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"
19 #include "llvm/ADT/Triple.h"
20 #include "llvm/ExecutionEngine/JITLink/JITLinkMemoryManager.h"
21 #include "llvm/ExecutionEngine/JITSymbol.h"
22 #include "llvm/ExecutionEngine/Orc/Shared/MemoryFlags.h"
23 #include "llvm/Support/Allocator.h"
24 #include "llvm/Support/BinaryStreamReader.h"
25 #include "llvm/Support/BinaryStreamWriter.h"
26 #include "llvm/Support/Endian.h"
27 #include "llvm/Support/Error.h"
28 #include "llvm/Support/FormatVariadic.h"
29 #include "llvm/Support/MathExtras.h"
30 #include "llvm/Support/MemoryBuffer.h"
31 #include <optional>
32 
33 #include <map>
34 #include <string>
35 #include <system_error>
36 
37 namespace llvm {
38 namespace jitlink {
39 
40 class LinkGraph;
41 class Symbol;
42 class Section;
43 
44 /// Base class for errors originating in JIT linker, e.g. missing relocation
45 /// support.
46 class JITLinkError : public ErrorInfo<JITLinkError> {
47 public:
48   static char ID;
49 
JITLinkError(Twine ErrMsg)50   JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}
51 
52   void log(raw_ostream &OS) const override;
getErrorMessage()53   const std::string &getErrorMessage() const { return ErrMsg; }
54   std::error_code convertToErrorCode() const override;
55 
56 private:
57   std::string ErrMsg;
58 };
59 
60 /// Represents fixups and constraints in the LinkGraph.
61 class Edge {
62 public:
63   using Kind = uint8_t;
64 
65   enum GenericEdgeKind : Kind {
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 
72   using OffsetT = uint32_t;
73   using AddendT = int64_t;
74 
Edge(Kind K,OffsetT Offset,Symbol & Target,AddendT Addend)75   Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
76       : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
77 
getOffset()78   OffsetT getOffset() const { return Offset; }
setOffset(OffsetT Offset)79   void setOffset(OffsetT Offset) { this->Offset = Offset; }
getKind()80   Kind getKind() const { return K; }
setKind(Kind K)81   void setKind(Kind K) { this->K = K; }
isRelocation()82   bool isRelocation() const { return K >= FirstRelocation; }
getRelocation()83   Kind getRelocation() const {
84     assert(isRelocation() && "Not a relocation edge");
85     return K - FirstRelocation;
86   }
isKeepAlive()87   bool isKeepAlive() const { return K >= FirstKeepAlive; }
getTarget()88   Symbol &getTarget() const { return *Target; }
setTarget(Symbol & Target)89   void setTarget(Symbol &Target) { this->Target = &Target; }
getAddend()90   AddendT getAddend() const { return Addend; }
setAddend(AddendT Addend)91   void setAddend(AddendT Addend) { this->Addend = Addend; }
92 
93 private:
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.
102 const char *getGenericEdgeKindName(Edge::Kind K);
103 
104 /// Base class for Addressable entities (externals, absolutes, blocks).
105 class Addressable {
106   friend class LinkGraph;
107 
108 protected:
Addressable(orc::ExecutorAddr Address,bool IsDefined)109   Addressable(orc::ExecutorAddr Address, bool IsDefined)
110       : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {}
111 
Addressable(orc::ExecutorAddr Address)112   Addressable(orc::ExecutorAddr Address)
113       : Address(Address), IsDefined(false), IsAbsolute(true) {
114     assert(!(IsDefined && IsAbsolute) &&
115            "Block cannot be both defined and absolute");
116   }
117 
118 public:
119   Addressable(const Addressable &) = delete;
120   Addressable &operator=(const Addressable &) = default;
121   Addressable(Addressable &&) = delete;
122   Addressable &operator=(Addressable &&) = default;
123 
getAddress()124   orc::ExecutorAddr getAddress() const { return Address; }
setAddress(orc::ExecutorAddr 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.
isDefined()129   bool isDefined() const { return static_cast<bool>(IsDefined); }
isAbsolute()130   bool isAbsolute() const { return static_cast<bool>(IsAbsolute); }
131 
132 private:
setAbsolute(bool IsAbsolute)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 
142 protected:
143   // bitfields for Block, allocated here to improve packing.
144   uint64_t ContentMutable : 1;
145   uint64_t P2Align : 5;
146   uint64_t AlignmentOffset : 56;
147 };
148 
149 using SectionOrdinal = unsigned;
150 
151 /// An Addressable with content and edges.
152 class Block : public Addressable {
153   friend class LinkGraph;
154 
155 private:
156   /// Create a zero-fill defined addressable.
Block(Section & Parent,orc::ExecutorAddrDiff Size,orc::ExecutorAddr Address,uint64_t Alignment,uint64_t AlignmentOffset)157   Block(Section &Parent, orc::ExecutorAddrDiff Size, orc::ExecutorAddr Address,
158         uint64_t Alignment, uint64_t AlignmentOffset)
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 ? countTrailingZeros(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.
Block(Section & Parent,ArrayRef<char> Content,orc::ExecutorAddr Address,uint64_t Alignment,uint64_t AlignmentOffset)173   Block(Section &Parent, ArrayRef<char> Content, orc::ExecutorAddr Address,
174         uint64_t Alignment, uint64_t AlignmentOffset)
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 ? countTrailingZeros(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.
Block(Section & Parent,MutableArrayRef<char> Content,orc::ExecutorAddr Address,uint64_t Alignment,uint64_t AlignmentOffset)192   Block(Section &Parent, MutableArrayRef<char> Content,
193         orc::ExecutorAddr Address, uint64_t Alignment, uint64_t AlignmentOffset)
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 ? countTrailingZeros(Alignment) : 0;
203     this->AlignmentOffset = AlignmentOffset;
204   }
205 
206 public:
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.
getSection()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).
isZeroFill()223   bool isZeroFill() const { return !Data; }
224 
225   /// Returns the size of this defined addressable.
getSize()226   size_t getSize() const { return Size; }
227 
228   /// Returns the address range of this defined addressable.
getRange()229   orc::ExecutorAddrRange getRange() const {
230     return orc::ExecutorAddrRange(getAddress(), getSize());
231   }
232 
233   /// Get the content for this block. Block must not be a zero-fill block.
getContent()234   ArrayRef<char> getContent() const {
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.
setContent(ArrayRef<char> Content)242   void setContent(ArrayRef<char> Content) {
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.
254   MutableArrayRef<char> getMutableContent(LinkGraph &G);
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.
getAlreadyMutableContent()261   MutableArrayRef<char> getAlreadyMutableContent() {
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.
setMutableContent(MutableArrayRef<char> MutableContent)271   void setMutableContent(MutableArrayRef<char> MutableContent) {
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.
isContentMutable()284   bool isContentMutable() const { return ContentMutable; }
285 
286   /// Get the alignment for this content.
getAlignment()287   uint64_t getAlignment() const { return 1ull << P2Align; }
288 
289   /// Set the alignment for this content.
setAlignment(uint64_t Alignment)290   void setAlignment(uint64_t Alignment) {
291     assert(isPowerOf2_64(Alignment) && "Alignment must be a power of two");
292     P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
293   }
294 
295   /// Get the alignment offset for this content.
getAlignmentOffset()296   uint64_t getAlignmentOffset() const { return AlignmentOffset; }
297 
298   /// Set the alignment offset for this content.
setAlignmentOffset(uint64_t AlignmentOffset)299   void setAlignmentOffset(uint64_t AlignmentOffset) {
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.
addEdge(Edge::Kind K,Edge::OffsetT Offset,Symbol & Target,Edge::AddendT Addend)306   void addEdge(Edge::Kind K, Edge::OffsetT Offset, Symbol &Target,
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.
addEdge(const Edge & E)315   void addEdge(const Edge &E) { Edges.push_back(E); }
316 
317   /// Return the list of edges attached to this content.
edges()318   iterator_range<edge_iterator> edges() {
319     return make_range(Edges.begin(), Edges.end());
320   }
321 
322   /// Returns the list of edges attached to this content.
edges()323   iterator_range<const_edge_iterator> edges() const {
324     return make_range(Edges.begin(), Edges.end());
325   }
326 
327   /// Return the size of the edges list.
edges_size()328   size_t edges_size() const { return Edges.size(); }
329 
330   /// Returns true if the list of edges is empty.
edges_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.
removeEdge(edge_iterator I)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.
getFixupAddress(const Edge & E)339   orc::ExecutorAddr getFixupAddress(const Edge &E) const {
340     return getAddress() + E.getOffset();
341   }
342 
343 private:
344   static constexpr uint64_t MaxAlignmentOffset = (1ULL << 56) - 1;
345 
setSection(Section & Parent)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.
alignToBlock(uint64_t Addr,Block & B)355 inline uint64_t alignToBlock(uint64_t Addr, Block &B) {
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.
alignToBlock(orc::ExecutorAddr Addr,Block & B)361 inline orc::ExecutorAddr alignToBlock(orc::ExecutorAddr Addr, Block &B) {
362   return orc::ExecutorAddr(alignToBlock(Addr.getValue(), B));
363 }
364 
365 /// Describes symbol linkage. This can be used to make resolve definition
366 /// clashes.
367 enum class Linkage : uint8_t {
368   Strong,
369   Weak,
370 };
371 
372 /// For errors and debugging output.
373 const char *getLinkageName(Linkage L);
374 
375 /// Defines the scope in which this symbol should be visible:
376 ///   Default -- Visible in the public interface of the linkage unit.
377 ///   Hidden -- Visible within the linkage unit, but not exported from it.
378 ///   Local -- Visible only within the LinkGraph.
379 enum class Scope : uint8_t {
380   Default,
381   Hidden,
382   Local
383 };
384 
385 /// For debugging output.
386 const char *getScopeName(Scope S);
387 
388 raw_ostream &operator<<(raw_ostream &OS, const Block &B);
389 
390 /// Symbol representation.
391 ///
392 /// Symbols represent locations within Addressable objects.
393 /// They can be either Named or Anonymous.
394 /// Anonymous symbols have neither linkage nor visibility, and must point at
395 /// ContentBlocks.
396 /// Named symbols may be in one of four states:
397 ///   - Null: Default initialized. Assignable, but otherwise unusable.
398 ///   - Defined: Has both linkage and visibility and points to a ContentBlock
399 ///   - Common: Has both linkage and visibility, points to a null Addressable.
400 ///   - External: Has neither linkage nor visibility, points to an external
401 ///     Addressable.
402 ///
403 class Symbol {
404   friend class LinkGraph;
405 
406 private:
Symbol(Addressable & Base,orc::ExecutorAddrDiff Offset,StringRef Name,orc::ExecutorAddrDiff Size,Linkage L,Scope S,bool IsLive,bool IsCallable)407   Symbol(Addressable &Base, orc::ExecutorAddrDiff Offset, StringRef Name,
408          orc::ExecutorAddrDiff Size, Linkage L, Scope S, bool IsLive,
409          bool IsCallable)
410       : Name(Name), Base(&Base), Offset(Offset), WeakRef(0), Size(Size) {
411     assert(Offset <= MaxOffset && "Offset out of range");
412     setLinkage(L);
413     setScope(S);
414     setLive(IsLive);
415     setCallable(IsCallable);
416   }
417 
constructExternal(BumpPtrAllocator & Allocator,Addressable & Base,StringRef Name,orc::ExecutorAddrDiff Size,Linkage L,bool WeaklyReferenced)418   static Symbol &constructExternal(BumpPtrAllocator &Allocator,
419                                    Addressable &Base, StringRef Name,
420                                    orc::ExecutorAddrDiff Size, Linkage L,
421                                    bool WeaklyReferenced) {
422     assert(!Base.isDefined() &&
423            "Cannot create external symbol from defined block");
424     assert(!Name.empty() && "External symbol name cannot be empty");
425     auto *Sym = Allocator.Allocate<Symbol>();
426     new (Sym) Symbol(Base, 0, Name, Size, L, Scope::Default, false, false);
427     Sym->setWeaklyReferenced(WeaklyReferenced);
428     return *Sym;
429   }
430 
constructAbsolute(BumpPtrAllocator & Allocator,Addressable & Base,StringRef Name,orc::ExecutorAddrDiff Size,Linkage L,Scope S,bool IsLive)431   static Symbol &constructAbsolute(BumpPtrAllocator &Allocator,
432                                    Addressable &Base, StringRef Name,
433                                    orc::ExecutorAddrDiff Size, Linkage L,
434                                    Scope S, bool IsLive) {
435     assert(!Base.isDefined() &&
436            "Cannot create absolute symbol from a defined block");
437     auto *Sym = Allocator.Allocate<Symbol>();
438     new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
439     return *Sym;
440   }
441 
constructAnonDef(BumpPtrAllocator & Allocator,Block & Base,orc::ExecutorAddrDiff Offset,orc::ExecutorAddrDiff Size,bool IsCallable,bool IsLive)442   static Symbol &constructAnonDef(BumpPtrAllocator &Allocator, Block &Base,
443                                   orc::ExecutorAddrDiff Offset,
444                                   orc::ExecutorAddrDiff Size, bool IsCallable,
445                                   bool IsLive) {
446     assert((Offset + Size) <= Base.getSize() &&
447            "Symbol extends past end of block");
448     auto *Sym = Allocator.Allocate<Symbol>();
449     new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
450                      Scope::Local, IsLive, IsCallable);
451     return *Sym;
452   }
453 
constructNamedDef(BumpPtrAllocator & Allocator,Block & Base,orc::ExecutorAddrDiff Offset,StringRef Name,orc::ExecutorAddrDiff Size,Linkage L,Scope S,bool IsLive,bool IsCallable)454   static Symbol &constructNamedDef(BumpPtrAllocator &Allocator, Block &Base,
455                                    orc::ExecutorAddrDiff Offset, StringRef Name,
456                                    orc::ExecutorAddrDiff Size, Linkage L,
457                                    Scope S, bool IsLive, bool IsCallable) {
458     assert((Offset + Size) <= Base.getSize() &&
459            "Symbol extends past end of block");
460     assert(!Name.empty() && "Name cannot be empty");
461     auto *Sym = Allocator.Allocate<Symbol>();
462     new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
463     return *Sym;
464   }
465 
466 public:
467   /// Create a null Symbol. This allows Symbols to be default initialized for
468   /// use in containers (e.g. as map values). Null symbols are only useful for
469   /// assigning to.
470   Symbol() = default;
471 
472   // Symbols are not movable or copyable.
473   Symbol(const Symbol &) = delete;
474   Symbol &operator=(const Symbol &) = delete;
475   Symbol(Symbol &&) = delete;
476   Symbol &operator=(Symbol &&) = delete;
477 
478   /// Returns true if this symbol has a name.
hasName()479   bool hasName() const { return !Name.empty(); }
480 
481   /// Returns the name of this symbol (empty if the symbol is anonymous).
getName()482   StringRef getName() const {
483     assert((!Name.empty() || getScope() == Scope::Local) &&
484            "Anonymous symbol has non-local scope");
485     return Name;
486   }
487 
488   /// Rename this symbol. The client is responsible for updating scope and
489   /// linkage if this name-change requires it.
setName(StringRef Name)490   void setName(StringRef Name) { this->Name = Name; }
491 
492   /// Returns true if this Symbol has content (potentially) defined within this
493   /// object file (i.e. is anything but an external or absolute symbol).
isDefined()494   bool isDefined() const {
495     assert(Base && "Attempt to access null symbol");
496     return Base->isDefined();
497   }
498 
499   /// Returns true if this symbol is live (i.e. should be treated as a root for
500   /// dead stripping).
isLive()501   bool isLive() const {
502     assert(Base && "Attempting to access null symbol");
503     return IsLive;
504   }
505 
506   /// Set this symbol's live bit.
setLive(bool IsLive)507   void setLive(bool IsLive) { this->IsLive = IsLive; }
508 
509   /// Returns true is this symbol is callable.
isCallable()510   bool isCallable() const { return IsCallable; }
511 
512   /// Set this symbol's callable bit.
setCallable(bool IsCallable)513   void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }
514 
515   /// Returns true if the underlying addressable is an unresolved external.
isExternal()516   bool isExternal() const {
517     assert(Base && "Attempt to access null symbol");
518     return !Base->isDefined() && !Base->isAbsolute();
519   }
520 
521   /// Returns true if the underlying addressable is an absolute symbol.
isAbsolute()522   bool isAbsolute() const {
523     assert(Base && "Attempt to access null symbol");
524     return Base->isAbsolute();
525   }
526 
527   /// Return the addressable that this symbol points to.
getAddressable()528   Addressable &getAddressable() {
529     assert(Base && "Cannot get underlying addressable for null symbol");
530     return *Base;
531   }
532 
533   /// Return the addressable that this symbol points to.
getAddressable()534   const Addressable &getAddressable() const {
535     assert(Base && "Cannot get underlying addressable for null symbol");
536     return *Base;
537   }
538 
539   /// Return the Block for this Symbol (Symbol must be defined).
getBlock()540   Block &getBlock() {
541     assert(Base && "Cannot get block for null symbol");
542     assert(Base->isDefined() && "Not a defined symbol");
543     return static_cast<Block &>(*Base);
544   }
545 
546   /// Return the Block for this Symbol (Symbol must be defined).
getBlock()547   const Block &getBlock() const {
548     assert(Base && "Cannot get block for null symbol");
549     assert(Base->isDefined() && "Not a defined symbol");
550     return static_cast<const Block &>(*Base);
551   }
552 
553   /// Returns the offset for this symbol within the underlying addressable.
getOffset()554   orc::ExecutorAddrDiff getOffset() const { return Offset; }
555 
556   /// Returns the address of this symbol.
getAddress()557   orc::ExecutorAddr getAddress() const { return Base->getAddress() + Offset; }
558 
559   /// Returns the size of this symbol.
getSize()560   orc::ExecutorAddrDiff getSize() const { return Size; }
561 
562   /// Set the size of this symbol.
setSize(orc::ExecutorAddrDiff Size)563   void setSize(orc::ExecutorAddrDiff Size) {
564     assert(Base && "Cannot set size for null Symbol");
565     assert((Size == 0 || Base->isDefined()) &&
566            "Non-zero size can only be set for defined symbols");
567     assert((Offset + Size <= static_cast<const Block &>(*Base).getSize()) &&
568            "Symbol size cannot extend past the end of its containing block");
569     this->Size = Size;
570   }
571 
572   /// Returns the address range of this symbol.
getRange()573   orc::ExecutorAddrRange getRange() const {
574     return orc::ExecutorAddrRange(getAddress(), getSize());
575   }
576 
577   /// Returns true if this symbol is backed by a zero-fill block.
578   /// This method may only be called on defined symbols.
isSymbolZeroFill()579   bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }
580 
581   /// Returns the content in the underlying block covered by this symbol.
582   /// This method may only be called on defined non-zero-fill symbols.
getSymbolContent()583   ArrayRef<char> getSymbolContent() const {
584     return getBlock().getContent().slice(Offset, Size);
585   }
586 
587   /// Get the linkage for this Symbol.
getLinkage()588   Linkage getLinkage() const { return static_cast<Linkage>(L); }
589 
590   /// Set the linkage for this Symbol.
setLinkage(Linkage L)591   void setLinkage(Linkage L) {
592     assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) &&
593            "Linkage can only be applied to defined named symbols");
594     this->L = static_cast<uint8_t>(L);
595   }
596 
597   /// Get the visibility for this Symbol.
getScope()598   Scope getScope() const { return static_cast<Scope>(S); }
599 
600   /// Set the visibility for this Symbol.
setScope(Scope S)601   void setScope(Scope S) {
602     assert((!Name.empty() || S == Scope::Local) &&
603            "Can not set anonymous symbol to non-local scope");
604     assert((S != Scope::Local || Base->isDefined() || Base->isAbsolute()) &&
605            "Invalid visibility for symbol type");
606     this->S = static_cast<uint8_t>(S);
607   }
608 
609   /// Returns true if this is a weakly referenced external symbol.
610   /// This method may only be called on external symbols.
isWeaklyReferenced()611   bool isWeaklyReferenced() const {
612     assert(isExternal() && "isWeaklyReferenced called on non-external");
613     return WeakRef;
614   }
615 
616   /// Set the WeaklyReferenced value for this symbol.
617   /// This method may only be called on external symbols.
setWeaklyReferenced(bool WeakRef)618   void setWeaklyReferenced(bool WeakRef) {
619     assert(isExternal() && "setWeaklyReferenced called on non-external");
620     this->WeakRef = WeakRef;
621   }
622 
623 private:
makeExternal(Addressable & A)624   void makeExternal(Addressable &A) {
625     assert(!A.isDefined() && !A.isAbsolute() &&
626            "Attempting to make external with defined or absolute block");
627     Base = &A;
628     Offset = 0;
629     setScope(Scope::Default);
630     IsLive = 0;
631     // note: Size, Linkage and IsCallable fields left unchanged.
632   }
633 
makeAbsolute(Addressable & A)634   void makeAbsolute(Addressable &A) {
635     assert(!A.isDefined() && A.isAbsolute() &&
636            "Attempting to make absolute with defined or external block");
637     Base = &A;
638     Offset = 0;
639   }
640 
setBlock(Block & B)641   void setBlock(Block &B) { Base = &B; }
642 
setOffset(orc::ExecutorAddrDiff NewOffset)643   void setOffset(orc::ExecutorAddrDiff NewOffset) {
644     assert(NewOffset <= MaxOffset && "Offset out of range");
645     Offset = NewOffset;
646   }
647 
648   static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
649 
650   // FIXME: A char* or SymbolStringPtr may pack better.
651   StringRef Name;
652   Addressable *Base = nullptr;
653   uint64_t Offset : 58;
654   uint64_t L : 1;
655   uint64_t S : 2;
656   uint64_t IsLive : 1;
657   uint64_t IsCallable : 1;
658   uint64_t WeakRef : 1;
659   size_t Size = 0;
660 };
661 
662 raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);
663 
664 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
665                StringRef EdgeKindName);
666 
667 /// Represents an object file section.
668 class Section {
669   friend class LinkGraph;
670 
671 private:
Section(StringRef Name,orc::MemProt Prot,SectionOrdinal SecOrdinal)672   Section(StringRef Name, orc::MemProt Prot, SectionOrdinal SecOrdinal)
673       : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {}
674 
675   using SymbolSet = DenseSet<Symbol *>;
676   using BlockSet = DenseSet<Block *>;
677 
678 public:
679   using symbol_iterator = SymbolSet::iterator;
680   using const_symbol_iterator = SymbolSet::const_iterator;
681 
682   using block_iterator = BlockSet::iterator;
683   using const_block_iterator = BlockSet::const_iterator;
684 
685   ~Section();
686 
687   // Sections are not movable or copyable.
688   Section(const Section &) = delete;
689   Section &operator=(const Section &) = delete;
690   Section(Section &&) = delete;
691   Section &operator=(Section &&) = delete;
692 
693   /// Returns the name of this section.
getName()694   StringRef getName() const { return Name; }
695 
696   /// Returns the protection flags for this section.
getMemProt()697   orc::MemProt getMemProt() const { return Prot; }
698 
699   /// Set the protection flags for this section.
setMemProt(orc::MemProt Prot)700   void setMemProt(orc::MemProt Prot) { this->Prot = Prot; }
701 
702   /// Get the deallocation policy for this section.
getMemDeallocPolicy()703   orc::MemDeallocPolicy getMemDeallocPolicy() const { return MDP; }
704 
705   /// Set the deallocation policy for this section.
setMemDeallocPolicy(orc::MemDeallocPolicy MDP)706   void setMemDeallocPolicy(orc::MemDeallocPolicy MDP) { this->MDP = MDP; }
707 
708   /// Returns the ordinal for this section.
getOrdinal()709   SectionOrdinal getOrdinal() const { return SecOrdinal; }
710 
711   /// Returns an iterator over the blocks defined in this section.
blocks()712   iterator_range<block_iterator> blocks() {
713     return make_range(Blocks.begin(), Blocks.end());
714   }
715 
716   /// Returns an iterator over the blocks defined in this section.
blocks()717   iterator_range<const_block_iterator> blocks() const {
718     return make_range(Blocks.begin(), Blocks.end());
719   }
720 
721   /// Returns the number of blocks in this section.
blocks_size()722   BlockSet::size_type blocks_size() const { return Blocks.size(); }
723 
724   /// Returns an iterator over the symbols defined in this section.
symbols()725   iterator_range<symbol_iterator> symbols() {
726     return make_range(Symbols.begin(), Symbols.end());
727   }
728 
729   /// Returns an iterator over the symbols defined in this section.
symbols()730   iterator_range<const_symbol_iterator> symbols() const {
731     return make_range(Symbols.begin(), Symbols.end());
732   }
733 
734   /// Return the number of symbols in this section.
symbols_size()735   SymbolSet::size_type symbols_size() const { return Symbols.size(); }
736 
737 private:
addSymbol(Symbol & Sym)738   void addSymbol(Symbol &Sym) {
739     assert(!Symbols.count(&Sym) && "Symbol is already in this section");
740     Symbols.insert(&Sym);
741   }
742 
removeSymbol(Symbol & Sym)743   void removeSymbol(Symbol &Sym) {
744     assert(Symbols.count(&Sym) && "symbol is not in this section");
745     Symbols.erase(&Sym);
746   }
747 
addBlock(Block & B)748   void addBlock(Block &B) {
749     assert(!Blocks.count(&B) && "Block is already in this section");
750     Blocks.insert(&B);
751   }
752 
removeBlock(Block & B)753   void removeBlock(Block &B) {
754     assert(Blocks.count(&B) && "Block is not in this section");
755     Blocks.erase(&B);
756   }
757 
transferContentTo(Section & DstSection)758   void transferContentTo(Section &DstSection) {
759     if (&DstSection == this)
760       return;
761     for (auto *S : Symbols)
762       DstSection.addSymbol(*S);
763     for (auto *B : Blocks)
764       DstSection.addBlock(*B);
765     Symbols.clear();
766     Blocks.clear();
767   }
768 
769   StringRef Name;
770   orc::MemProt Prot;
771   orc::MemDeallocPolicy MDP = orc::MemDeallocPolicy::Standard;
772   SectionOrdinal SecOrdinal = 0;
773   BlockSet Blocks;
774   SymbolSet Symbols;
775 };
776 
777 /// Represents a section address range via a pair of Block pointers
778 /// to the first and last Blocks in the section.
779 class SectionRange {
780 public:
781   SectionRange() = default;
SectionRange(const Section & Sec)782   SectionRange(const Section &Sec) {
783     if (Sec.blocks().empty())
784       return;
785     First = Last = *Sec.blocks().begin();
786     for (auto *B : Sec.blocks()) {
787       if (B->getAddress() < First->getAddress())
788         First = B;
789       if (B->getAddress() > Last->getAddress())
790         Last = B;
791     }
792   }
getFirstBlock()793   Block *getFirstBlock() const {
794     assert((!Last || First) && "First can not be null if end is non-null");
795     return First;
796   }
getLastBlock()797   Block *getLastBlock() const {
798     assert((First || !Last) && "Last can not be null if start is non-null");
799     return Last;
800   }
empty()801   bool empty() const {
802     assert((First || !Last) && "Last can not be null if start is non-null");
803     return !First;
804   }
getStart()805   orc::ExecutorAddr getStart() const {
806     return First ? First->getAddress() : orc::ExecutorAddr();
807   }
getEnd()808   orc::ExecutorAddr getEnd() const {
809     return Last ? Last->getAddress() + Last->getSize() : orc::ExecutorAddr();
810   }
getSize()811   orc::ExecutorAddrDiff getSize() const { return getEnd() - getStart(); }
812 
getRange()813   orc::ExecutorAddrRange getRange() const {
814     return orc::ExecutorAddrRange(getStart(), getEnd());
815   }
816 
817 private:
818   Block *First = nullptr;
819   Block *Last = nullptr;
820 };
821 
822 class LinkGraph {
823 private:
824   using SectionList = std::vector<std::unique_ptr<Section>>;
825   using ExternalSymbolSet = DenseSet<Symbol *>;
826   using BlockSet = DenseSet<Block *>;
827 
828   template <typename... ArgTs>
createAddressable(ArgTs &&...Args)829   Addressable &createAddressable(ArgTs &&... Args) {
830     Addressable *A =
831         reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
832     new (A) Addressable(std::forward<ArgTs>(Args)...);
833     return *A;
834   }
835 
destroyAddressable(Addressable & A)836   void destroyAddressable(Addressable &A) {
837     A.~Addressable();
838     Allocator.Deallocate(&A);
839   }
840 
createBlock(ArgTs &&...Args)841   template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) {
842     Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>());
843     new (B) Block(std::forward<ArgTs>(Args)...);
844     B->getSection().addBlock(*B);
845     return *B;
846   }
847 
destroyBlock(Block & B)848   void destroyBlock(Block &B) {
849     B.~Block();
850     Allocator.Deallocate(&B);
851   }
852 
destroySymbol(Symbol & S)853   void destroySymbol(Symbol &S) {
854     S.~Symbol();
855     Allocator.Deallocate(&S);
856   }
857 
getSectionBlocks(Section & S)858   static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) {
859     return S.blocks();
860   }
861 
862   static iterator_range<Section::const_block_iterator>
getSectionConstBlocks(Section & S)863   getSectionConstBlocks(Section &S) {
864     return S.blocks();
865   }
866 
867   static iterator_range<Section::symbol_iterator>
getSectionSymbols(Section & S)868   getSectionSymbols(Section &S) {
869     return S.symbols();
870   }
871 
872   static iterator_range<Section::const_symbol_iterator>
getSectionConstSymbols(Section & S)873   getSectionConstSymbols(Section &S) {
874     return S.symbols();
875   }
876 
877 public:
878   using external_symbol_iterator = ExternalSymbolSet::iterator;
879 
880   using section_iterator = pointee_iterator<SectionList::iterator>;
881   using const_section_iterator = pointee_iterator<SectionList::const_iterator>;
882 
883   template <typename OuterItrT, typename InnerItrT, typename T,
884             iterator_range<InnerItrT> getInnerRange(
885                 typename OuterItrT::reference)>
886   class nested_collection_iterator
887       : public iterator_facade_base<
888             nested_collection_iterator<OuterItrT, InnerItrT, T, getInnerRange>,
889             std::forward_iterator_tag, T> {
890   public:
891     nested_collection_iterator() = default;
892 
nested_collection_iterator(OuterItrT OuterI,OuterItrT OuterE)893     nested_collection_iterator(OuterItrT OuterI, OuterItrT OuterE)
894         : OuterI(OuterI), OuterE(OuterE),
895           InnerI(getInnerBegin(OuterI, OuterE)) {
896       moveToNonEmptyInnerOrEnd();
897     }
898 
899     bool operator==(const nested_collection_iterator &RHS) const {
900       return (OuterI == RHS.OuterI) && (InnerI == RHS.InnerI);
901     }
902 
903     T operator*() const {
904       assert(InnerI != getInnerRange(*OuterI).end() && "Dereferencing end?");
905       return *InnerI;
906     }
907 
908     nested_collection_iterator operator++() {
909       ++InnerI;
910       moveToNonEmptyInnerOrEnd();
911       return *this;
912     }
913 
914   private:
getInnerBegin(OuterItrT OuterI,OuterItrT OuterE)915     static InnerItrT getInnerBegin(OuterItrT OuterI, OuterItrT OuterE) {
916       return OuterI != OuterE ? getInnerRange(*OuterI).begin() : InnerItrT();
917     }
918 
moveToNonEmptyInnerOrEnd()919     void moveToNonEmptyInnerOrEnd() {
920       while (OuterI != OuterE && InnerI == getInnerRange(*OuterI).end()) {
921         ++OuterI;
922         InnerI = getInnerBegin(OuterI, OuterE);
923       }
924     }
925 
926     OuterItrT OuterI, OuterE;
927     InnerItrT InnerI;
928   };
929 
930   using defined_symbol_iterator =
931       nested_collection_iterator<const_section_iterator,
932                                  Section::symbol_iterator, Symbol *,
933                                  getSectionSymbols>;
934 
935   using const_defined_symbol_iterator =
936       nested_collection_iterator<const_section_iterator,
937                                  Section::const_symbol_iterator, const Symbol *,
938                                  getSectionConstSymbols>;
939 
940   using block_iterator = nested_collection_iterator<const_section_iterator,
941                                                     Section::block_iterator,
942                                                     Block *, getSectionBlocks>;
943 
944   using const_block_iterator =
945       nested_collection_iterator<const_section_iterator,
946                                  Section::const_block_iterator, const Block *,
947                                  getSectionConstBlocks>;
948 
949   using GetEdgeKindNameFunction = const char *(*)(Edge::Kind);
950 
LinkGraph(std::string Name,const Triple & TT,unsigned PointerSize,support::endianness Endianness,GetEdgeKindNameFunction GetEdgeKindName)951   LinkGraph(std::string Name, const Triple &TT, unsigned PointerSize,
952             support::endianness Endianness,
953             GetEdgeKindNameFunction GetEdgeKindName)
954       : Name(std::move(Name)), TT(TT), PointerSize(PointerSize),
955         Endianness(Endianness), GetEdgeKindName(std::move(GetEdgeKindName)) {}
956 
957   LinkGraph(const LinkGraph &) = delete;
958   LinkGraph &operator=(const LinkGraph &) = delete;
959   LinkGraph(LinkGraph &&) = delete;
960   LinkGraph &operator=(LinkGraph &&) = delete;
961 
962   /// Returns the name of this graph (usually the name of the original
963   /// underlying MemoryBuffer).
getName()964   const std::string &getName() const { return Name; }
965 
966   /// Returns the target triple for this Graph.
getTargetTriple()967   const Triple &getTargetTriple() const { return TT; }
968 
969   /// Returns the pointer size for use in this graph.
getPointerSize()970   unsigned getPointerSize() const { return PointerSize; }
971 
972   /// Returns the endianness of content in this graph.
getEndianness()973   support::endianness getEndianness() const { return Endianness; }
974 
getEdgeKindName(Edge::Kind K)975   const char *getEdgeKindName(Edge::Kind K) const { return GetEdgeKindName(K); }
976 
977   /// Allocate a mutable buffer of the given size using the LinkGraph's
978   /// allocator.
allocateBuffer(size_t Size)979   MutableArrayRef<char> allocateBuffer(size_t Size) {
980     return {Allocator.Allocate<char>(Size), Size};
981   }
982 
983   /// Allocate a copy of the given string using the LinkGraph's allocator.
984   /// This can be useful when renaming symbols or adding new content to the
985   /// graph.
allocateContent(ArrayRef<char> Source)986   MutableArrayRef<char> allocateContent(ArrayRef<char> Source) {
987     auto *AllocatedBuffer = Allocator.Allocate<char>(Source.size());
988     llvm::copy(Source, AllocatedBuffer);
989     return MutableArrayRef<char>(AllocatedBuffer, Source.size());
990   }
991 
992   /// Allocate a copy of the given string using the LinkGraph's allocator.
993   /// This can be useful when renaming symbols or adding new content to the
994   /// graph.
995   ///
996   /// Note: This Twine-based overload requires an extra string copy and an
997   /// extra heap allocation for large strings. The ArrayRef<char> overload
998   /// should be preferred where possible.
allocateString(Twine Source)999   MutableArrayRef<char> allocateString(Twine Source) {
1000     SmallString<256> TmpBuffer;
1001     auto SourceStr = Source.toStringRef(TmpBuffer);
1002     auto *AllocatedBuffer = Allocator.Allocate<char>(SourceStr.size());
1003     llvm::copy(SourceStr, AllocatedBuffer);
1004     return MutableArrayRef<char>(AllocatedBuffer, SourceStr.size());
1005   }
1006 
1007   /// Create a section with the given name, protection flags, and alignment.
createSection(StringRef Name,orc::MemProt Prot)1008   Section &createSection(StringRef Name, orc::MemProt Prot) {
1009     assert(llvm::none_of(Sections,
1010                          [&](std::unique_ptr<Section> &Sec) {
1011                            return Sec->getName() == Name;
1012                          }) &&
1013            "Duplicate section name");
1014     std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size()));
1015     Sections.push_back(std::move(Sec));
1016     return *Sections.back();
1017   }
1018 
1019   /// Create a content block.
createContentBlock(Section & Parent,ArrayRef<char> Content,orc::ExecutorAddr Address,uint64_t Alignment,uint64_t AlignmentOffset)1020   Block &createContentBlock(Section &Parent, ArrayRef<char> Content,
1021                             orc::ExecutorAddr Address, uint64_t Alignment,
1022                             uint64_t AlignmentOffset) {
1023     return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
1024   }
1025 
1026   /// Create a content block with initially mutable data.
createMutableContentBlock(Section & Parent,MutableArrayRef<char> MutableContent,orc::ExecutorAddr Address,uint64_t Alignment,uint64_t AlignmentOffset)1027   Block &createMutableContentBlock(Section &Parent,
1028                                    MutableArrayRef<char> MutableContent,
1029                                    orc::ExecutorAddr Address,
1030                                    uint64_t Alignment,
1031                                    uint64_t AlignmentOffset) {
1032     return createBlock(Parent, MutableContent, Address, Alignment,
1033                        AlignmentOffset);
1034   }
1035 
1036   /// Create a content block with initially mutable data of the given size.
1037   /// Content will be allocated via the LinkGraph's allocateBuffer method.
1038   /// By default the memory will be zero-initialized. Passing false for
1039   /// ZeroInitialize will prevent this.
1040   Block &createMutableContentBlock(Section &Parent, size_t ContentSize,
1041                                    orc::ExecutorAddr Address,
1042                                    uint64_t Alignment, uint64_t AlignmentOffset,
1043                                    bool ZeroInitialize = true) {
1044     auto Content = allocateContent(ContentSize);
1045     if (ZeroInitialize)
1046       memset(Content.data(), 0, Content.size());
1047     return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
1048   }
1049 
1050   /// Create a zero-fill block.
createZeroFillBlock(Section & Parent,orc::ExecutorAddrDiff Size,orc::ExecutorAddr Address,uint64_t Alignment,uint64_t AlignmentOffset)1051   Block &createZeroFillBlock(Section &Parent, orc::ExecutorAddrDiff Size,
1052                              orc::ExecutorAddr Address, uint64_t Alignment,
1053                              uint64_t AlignmentOffset) {
1054     return createBlock(Parent, Size, Address, Alignment, AlignmentOffset);
1055   }
1056 
1057   /// Returns a BinaryStreamReader for the given block.
getBlockContentReader(Block & B)1058   BinaryStreamReader getBlockContentReader(Block &B) {
1059     ArrayRef<uint8_t> C(
1060         reinterpret_cast<const uint8_t *>(B.getContent().data()), B.getSize());
1061     return BinaryStreamReader(C, getEndianness());
1062   }
1063 
1064   /// Returns a BinaryStreamWriter for the given block.
1065   /// This will call getMutableContent to obtain mutable content for the block.
getBlockContentWriter(Block & B)1066   BinaryStreamWriter getBlockContentWriter(Block &B) {
1067     MutableArrayRef<uint8_t> C(
1068         reinterpret_cast<uint8_t *>(B.getMutableContent(*this).data()),
1069         B.getSize());
1070     return BinaryStreamWriter(C, getEndianness());
1071   }
1072 
1073   /// Cache type for the splitBlock function.
1074   using SplitBlockCache = std::optional<SmallVector<Symbol *, 8>>;
1075 
1076   /// Splits block B at the given index which must be greater than zero.
1077   /// If SplitIndex == B.getSize() then this function is a no-op and returns B.
1078   /// If SplitIndex < B.getSize() then this function returns a new block
1079   /// covering the range [ 0, SplitIndex ), and B is modified to cover the range
1080   /// [ SplitIndex, B.size() ).
1081   ///
1082   /// The optional Cache parameter can be used to speed up repeated calls to
1083   /// splitBlock for a single block. If the value is None the cache will be
1084   /// treated as uninitialized and splitBlock will populate it. Otherwise it
1085   /// is assumed to contain the list of Symbols pointing at B, sorted in
1086   /// descending order of offset.
1087   ///
1088   /// Notes:
1089   ///
1090   /// 1. splitBlock must be used with care. Splitting a block may cause
1091   ///    incoming edges to become invalid if the edge target subexpression
1092   ///    points outside the bounds of the newly split target block (E.g. an
1093   ///    edge 'S + 10 : Pointer64' where S points to a newly split block
1094   ///    whose size is less than 10). No attempt is made to detect invalidation
1095   ///    of incoming edges, as in general this requires context that the
1096   ///    LinkGraph does not have. Clients are responsible for ensuring that
1097   ///    splitBlock is not used in a way that invalidates edges.
1098   ///
1099   /// 2. The newly introduced block will have a new ordinal which will be
1100   ///    higher than any other ordinals in the section. Clients are responsible
1101   ///    for re-assigning block ordinals to restore a compatible order if
1102   ///    needed.
1103   ///
1104   /// 3. The cache is not automatically updated if new symbols are introduced
1105   ///    between calls to splitBlock. Any newly introduced symbols may be
1106   ///    added to the cache manually (descending offset order must be
1107   ///    preserved), or the cache can be set to None and rebuilt by
1108   ///    splitBlock on the next call.
1109   Block &splitBlock(Block &B, size_t SplitIndex,
1110                     SplitBlockCache *Cache = nullptr);
1111 
1112   /// Add an external symbol.
1113   /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
1114   /// size is not known, you should substitute '0'.
1115   /// The IsWeaklyReferenced argument determines whether the symbol must be
1116   /// present during lookup: Externals that are strongly referenced must be
1117   /// found or an error will be emitted. Externals that are weakly referenced
1118   /// are permitted to be undefined, in which case they are assigned an address
1119   /// of 0.
addExternalSymbol(StringRef Name,orc::ExecutorAddrDiff Size,bool IsWeaklyReferenced)1120   Symbol &addExternalSymbol(StringRef Name, orc::ExecutorAddrDiff Size,
1121                             bool IsWeaklyReferenced) {
1122     assert(llvm::count_if(ExternalSymbols,
1123                           [&](const Symbol *Sym) {
1124                             return Sym->getName() == Name;
1125                           }) == 0 &&
1126            "Duplicate external symbol");
1127     auto &Sym = Symbol::constructExternal(
1128         Allocator, createAddressable(orc::ExecutorAddr(), false), Name, Size,
1129         Linkage::Strong, IsWeaklyReferenced);
1130     ExternalSymbols.insert(&Sym);
1131     return Sym;
1132   }
1133 
1134   /// Add an absolute symbol.
addAbsoluteSymbol(StringRef Name,orc::ExecutorAddr Address,orc::ExecutorAddrDiff Size,Linkage L,Scope S,bool IsLive)1135   Symbol &addAbsoluteSymbol(StringRef Name, orc::ExecutorAddr Address,
1136                             orc::ExecutorAddrDiff Size, Linkage L, Scope S,
1137                             bool IsLive) {
1138     assert((S == Scope::Local || llvm::count_if(AbsoluteSymbols,
1139                                                [&](const Symbol *Sym) {
1140                                                  return Sym->getName() == Name;
1141                                                }) == 0) &&
1142                                     "Duplicate absolute symbol");
1143     auto &Sym = Symbol::constructAbsolute(Allocator, createAddressable(Address),
1144                                           Name, Size, L, S, IsLive);
1145     AbsoluteSymbols.insert(&Sym);
1146     return Sym;
1147   }
1148 
1149   /// Add an anonymous symbol.
addAnonymousSymbol(Block & Content,orc::ExecutorAddrDiff Offset,orc::ExecutorAddrDiff Size,bool IsCallable,bool IsLive)1150   Symbol &addAnonymousSymbol(Block &Content, orc::ExecutorAddrDiff Offset,
1151                              orc::ExecutorAddrDiff Size, bool IsCallable,
1152                              bool IsLive) {
1153     auto &Sym = Symbol::constructAnonDef(Allocator, Content, Offset, Size,
1154                                          IsCallable, IsLive);
1155     Content.getSection().addSymbol(Sym);
1156     return Sym;
1157   }
1158 
1159   /// Add a named symbol.
addDefinedSymbol(Block & Content,orc::ExecutorAddrDiff Offset,StringRef Name,orc::ExecutorAddrDiff Size,Linkage L,Scope S,bool IsCallable,bool IsLive)1160   Symbol &addDefinedSymbol(Block &Content, orc::ExecutorAddrDiff Offset,
1161                            StringRef Name, orc::ExecutorAddrDiff Size,
1162                            Linkage L, Scope S, bool IsCallable, bool IsLive) {
1163     assert((S == Scope::Local || llvm::count_if(defined_symbols(),
1164                                                 [&](const Symbol *Sym) {
1165                                                   return Sym->getName() == Name;
1166                                                 }) == 0) &&
1167            "Duplicate defined symbol");
1168     auto &Sym = Symbol::constructNamedDef(Allocator, Content, Offset, Name,
1169                                           Size, L, S, IsLive, IsCallable);
1170     Content.getSection().addSymbol(Sym);
1171     return Sym;
1172   }
1173 
sections()1174   iterator_range<section_iterator> sections() {
1175     return make_range(section_iterator(Sections.begin()),
1176                       section_iterator(Sections.end()));
1177   }
1178 
sections_size()1179   SectionList::size_type sections_size() const { return Sections.size(); }
1180 
1181   /// Returns the section with the given name if it exists, otherwise returns
1182   /// null.
findSectionByName(StringRef Name)1183   Section *findSectionByName(StringRef Name) {
1184     for (auto &S : sections())
1185       if (S.getName() == Name)
1186         return &S;
1187     return nullptr;
1188   }
1189 
blocks()1190   iterator_range<block_iterator> blocks() {
1191     return make_range(block_iterator(Sections.begin(), Sections.end()),
1192                       block_iterator(Sections.end(), Sections.end()));
1193   }
1194 
blocks()1195   iterator_range<const_block_iterator> blocks() const {
1196     return make_range(const_block_iterator(Sections.begin(), Sections.end()),
1197                       const_block_iterator(Sections.end(), Sections.end()));
1198   }
1199 
external_symbols()1200   iterator_range<external_symbol_iterator> external_symbols() {
1201     return make_range(ExternalSymbols.begin(), ExternalSymbols.end());
1202   }
1203 
absolute_symbols()1204   iterator_range<external_symbol_iterator> absolute_symbols() {
1205     return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
1206   }
1207 
defined_symbols()1208   iterator_range<defined_symbol_iterator> defined_symbols() {
1209     return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()),
1210                       defined_symbol_iterator(Sections.end(), Sections.end()));
1211   }
1212 
defined_symbols()1213   iterator_range<const_defined_symbol_iterator> defined_symbols() const {
1214     return make_range(
1215         const_defined_symbol_iterator(Sections.begin(), Sections.end()),
1216         const_defined_symbol_iterator(Sections.end(), Sections.end()));
1217   }
1218 
1219   /// Make the given symbol external (must not already be external).
1220   ///
1221   /// Symbol size, linkage and callability will be left unchanged. Symbol scope
1222   /// will be set to Default, and offset will be reset to 0.
makeExternal(Symbol & Sym)1223   void makeExternal(Symbol &Sym) {
1224     assert(!Sym.isExternal() && "Symbol is already external");
1225     if (Sym.isAbsolute()) {
1226       assert(AbsoluteSymbols.count(&Sym) &&
1227              "Sym is not in the absolute symbols set");
1228       assert(Sym.getOffset() == 0 && "Absolute not at offset 0");
1229       AbsoluteSymbols.erase(&Sym);
1230       auto &A = Sym.getAddressable();
1231       A.setAbsolute(false);
1232       A.setAddress(orc::ExecutorAddr());
1233     } else {
1234       assert(Sym.isDefined() && "Sym is not a defined symbol");
1235       Section &Sec = Sym.getBlock().getSection();
1236       Sec.removeSymbol(Sym);
1237       Sym.makeExternal(createAddressable(orc::ExecutorAddr(), false));
1238     }
1239     ExternalSymbols.insert(&Sym);
1240   }
1241 
1242   /// Make the given symbol an absolute with the given address (must not already
1243   /// be absolute).
1244   ///
1245   /// The symbol's size, linkage, and callability, and liveness will be left
1246   /// unchanged, and its offset will be reset to 0.
1247   ///
1248   /// If the symbol was external then its scope will be set to local, otherwise
1249   /// it will be left unchanged.
makeAbsolute(Symbol & Sym,orc::ExecutorAddr Address)1250   void makeAbsolute(Symbol &Sym, orc::ExecutorAddr Address) {
1251     assert(!Sym.isAbsolute() && "Symbol is already absolute");
1252     if (Sym.isExternal()) {
1253       assert(ExternalSymbols.count(&Sym) &&
1254              "Sym is not in the absolute symbols set");
1255       assert(Sym.getOffset() == 0 && "External is not at offset 0");
1256       ExternalSymbols.erase(&Sym);
1257       auto &A = Sym.getAddressable();
1258       A.setAbsolute(true);
1259       A.setAddress(Address);
1260       Sym.setScope(Scope::Local);
1261     } else {
1262       assert(Sym.isDefined() && "Sym is not a defined symbol");
1263       Section &Sec = Sym.getBlock().getSection();
1264       Sec.removeSymbol(Sym);
1265       Sym.makeAbsolute(createAddressable(Address));
1266     }
1267     AbsoluteSymbols.insert(&Sym);
1268   }
1269 
1270   /// Turn an absolute or external symbol into a defined one by attaching it to
1271   /// a block. Symbol must not already be defined.
makeDefined(Symbol & Sym,Block & Content,orc::ExecutorAddrDiff Offset,orc::ExecutorAddrDiff Size,Linkage L,Scope S,bool IsLive)1272   void makeDefined(Symbol &Sym, Block &Content, orc::ExecutorAddrDiff Offset,
1273                    orc::ExecutorAddrDiff Size, Linkage L, Scope S,
1274                    bool IsLive) {
1275     assert(!Sym.isDefined() && "Sym is already a defined symbol");
1276     if (Sym.isAbsolute()) {
1277       assert(AbsoluteSymbols.count(&Sym) &&
1278              "Symbol is not in the absolutes set");
1279       AbsoluteSymbols.erase(&Sym);
1280     } else {
1281       assert(ExternalSymbols.count(&Sym) &&
1282              "Symbol is not in the externals set");
1283       ExternalSymbols.erase(&Sym);
1284     }
1285     Addressable &OldBase = *Sym.Base;
1286     Sym.setBlock(Content);
1287     Sym.setOffset(Offset);
1288     Sym.setSize(Size);
1289     Sym.setLinkage(L);
1290     Sym.setScope(S);
1291     Sym.setLive(IsLive);
1292     Content.getSection().addSymbol(Sym);
1293     destroyAddressable(OldBase);
1294   }
1295 
1296   /// Transfer a defined symbol from one block to another.
1297   ///
1298   /// The symbol's offset within DestBlock is set to NewOffset.
1299   ///
1300   /// If ExplicitNewSize is given as None then the size of the symbol will be
1301   /// checked and auto-truncated to at most the size of the remainder (from the
1302   /// given offset) of the size of the new block.
1303   ///
1304   /// All other symbol attributes are unchanged.
1305   void
transferDefinedSymbol(Symbol & Sym,Block & DestBlock,orc::ExecutorAddrDiff NewOffset,std::optional<orc::ExecutorAddrDiff> ExplicitNewSize)1306   transferDefinedSymbol(Symbol &Sym, Block &DestBlock,
1307                         orc::ExecutorAddrDiff NewOffset,
1308                         std::optional<orc::ExecutorAddrDiff> ExplicitNewSize) {
1309     auto &OldSection = Sym.getBlock().getSection();
1310     Sym.setBlock(DestBlock);
1311     Sym.setOffset(NewOffset);
1312     if (ExplicitNewSize)
1313       Sym.setSize(*ExplicitNewSize);
1314     else {
1315       auto RemainingBlockSize = DestBlock.getSize() - NewOffset;
1316       if (Sym.getSize() > RemainingBlockSize)
1317         Sym.setSize(RemainingBlockSize);
1318     }
1319     if (&DestBlock.getSection() != &OldSection) {
1320       OldSection.removeSymbol(Sym);
1321       DestBlock.getSection().addSymbol(Sym);
1322     }
1323   }
1324 
1325   /// Transfers the given Block and all Symbols pointing to it to the given
1326   /// Section.
1327   ///
1328   /// No attempt is made to check compatibility of the source and destination
1329   /// sections. Blocks may be moved between sections with incompatible
1330   /// permissions (e.g. from data to text). The client is responsible for
1331   /// ensuring that this is safe.
transferBlock(Block & B,Section & NewSection)1332   void transferBlock(Block &B, Section &NewSection) {
1333     auto &OldSection = B.getSection();
1334     if (&OldSection == &NewSection)
1335       return;
1336     SmallVector<Symbol *> AttachedSymbols;
1337     for (auto *S : OldSection.symbols())
1338       if (&S->getBlock() == &B)
1339         AttachedSymbols.push_back(S);
1340     for (auto *S : AttachedSymbols) {
1341       OldSection.removeSymbol(*S);
1342       NewSection.addSymbol(*S);
1343     }
1344     OldSection.removeBlock(B);
1345     NewSection.addBlock(B);
1346   }
1347 
1348   /// Move all blocks and symbols from the source section to the destination
1349   /// section.
1350   ///
1351   /// If PreserveSrcSection is true (or SrcSection and DstSection are the same)
1352   /// then SrcSection is preserved, otherwise it is removed (the default).
1353   void mergeSections(Section &DstSection, Section &SrcSection,
1354                      bool PreserveSrcSection = false) {
1355     if (&DstSection == &SrcSection)
1356       return;
1357     for (auto *B : SrcSection.blocks())
1358       B->setSection(DstSection);
1359     SrcSection.transferContentTo(DstSection);
1360     if (!PreserveSrcSection)
1361       removeSection(SrcSection);
1362   }
1363 
1364   /// Removes an external symbol. Also removes the underlying Addressable.
removeExternalSymbol(Symbol & Sym)1365   void removeExternalSymbol(Symbol &Sym) {
1366     assert(!Sym.isDefined() && !Sym.isAbsolute() &&
1367            "Sym is not an external symbol");
1368     assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set");
1369     ExternalSymbols.erase(&Sym);
1370     Addressable &Base = *Sym.Base;
1371     assert(llvm::none_of(ExternalSymbols,
1372                          [&](Symbol *AS) { return AS->Base == &Base; }) &&
1373            "Base addressable still in use");
1374     destroySymbol(Sym);
1375     destroyAddressable(Base);
1376   }
1377 
1378   /// Remove an absolute symbol. Also removes the underlying Addressable.
removeAbsoluteSymbol(Symbol & Sym)1379   void removeAbsoluteSymbol(Symbol &Sym) {
1380     assert(!Sym.isDefined() && Sym.isAbsolute() &&
1381            "Sym is not an absolute symbol");
1382     assert(AbsoluteSymbols.count(&Sym) &&
1383            "Symbol is not in the absolute symbols set");
1384     AbsoluteSymbols.erase(&Sym);
1385     Addressable &Base = *Sym.Base;
1386     assert(llvm::none_of(ExternalSymbols,
1387                          [&](Symbol *AS) { return AS->Base == &Base; }) &&
1388            "Base addressable still in use");
1389     destroySymbol(Sym);
1390     destroyAddressable(Base);
1391   }
1392 
1393   /// Removes defined symbols. Does not remove the underlying block.
removeDefinedSymbol(Symbol & Sym)1394   void removeDefinedSymbol(Symbol &Sym) {
1395     assert(Sym.isDefined() && "Sym is not a defined symbol");
1396     Sym.getBlock().getSection().removeSymbol(Sym);
1397     destroySymbol(Sym);
1398   }
1399 
1400   /// Remove a block. The block reference is defunct after calling this
1401   /// function and should no longer be used.
removeBlock(Block & B)1402   void removeBlock(Block &B) {
1403     assert(llvm::none_of(B.getSection().symbols(),
1404                          [&](const Symbol *Sym) {
1405                            return &Sym->getBlock() == &B;
1406                          }) &&
1407            "Block still has symbols attached");
1408     B.getSection().removeBlock(B);
1409     destroyBlock(B);
1410   }
1411 
1412   /// Remove a section. The section reference is defunct after calling this
1413   /// function and should no longer be used.
removeSection(Section & Sec)1414   void removeSection(Section &Sec) {
1415     auto I = llvm::find_if(Sections, [&Sec](const std::unique_ptr<Section> &S) {
1416       return S.get() == &Sec;
1417     });
1418     assert(I != Sections.end() && "Section does not appear in this graph");
1419     Sections.erase(I);
1420   }
1421 
1422   /// Accessor for the AllocActions object for this graph. This can be used to
1423   /// register allocation action calls prior to finalization.
1424   ///
1425   /// Accessing this object after finalization will result in undefined
1426   /// behavior.
allocActions()1427   orc::shared::AllocActions &allocActions() { return AAs; }
1428 
1429   /// Dump the graph.
1430   void dump(raw_ostream &OS);
1431 
1432 private:
1433   // Put the BumpPtrAllocator first so that we don't free any of the underlying
1434   // memory until the Symbol/Addressable destructors have been run.
1435   BumpPtrAllocator Allocator;
1436 
1437   std::string Name;
1438   Triple TT;
1439   unsigned PointerSize;
1440   support::endianness Endianness;
1441   GetEdgeKindNameFunction GetEdgeKindName = nullptr;
1442   SectionList Sections;
1443   ExternalSymbolSet ExternalSymbols;
1444   ExternalSymbolSet AbsoluteSymbols;
1445   orc::shared::AllocActions AAs;
1446 };
1447 
getMutableContent(LinkGraph & G)1448 inline MutableArrayRef<char> Block::getMutableContent(LinkGraph &G) {
1449   if (!ContentMutable)
1450     setMutableContent(G.allocateContent({Data, Size}));
1451   return MutableArrayRef<char>(const_cast<char *>(Data), Size);
1452 }
1453 
1454 /// Enables easy lookup of blocks by addresses.
1455 class BlockAddressMap {
1456 public:
1457   using AddrToBlockMap = std::map<orc::ExecutorAddr, Block *>;
1458   using const_iterator = AddrToBlockMap::const_iterator;
1459 
1460   /// A block predicate that always adds all blocks.
includeAllBlocks(const Block & B)1461   static bool includeAllBlocks(const Block &B) { return true; }
1462 
1463   /// A block predicate that always includes blocks with non-null addresses.
includeNonNull(const Block & B)1464   static bool includeNonNull(const Block &B) { return !!B.getAddress(); }
1465 
1466   BlockAddressMap() = default;
1467 
1468   /// Add a block to the map. Returns an error if the block overlaps with any
1469   /// existing block.
1470   template <typename PredFn = decltype(includeAllBlocks)>
1471   Error addBlock(Block &B, PredFn Pred = includeAllBlocks) {
1472     if (!Pred(B))
1473       return Error::success();
1474 
1475     auto I = AddrToBlock.upper_bound(B.getAddress());
1476 
1477     // If we're not at the end of the map, check for overlap with the next
1478     // element.
1479     if (I != AddrToBlock.end()) {
1480       if (B.getAddress() + B.getSize() > I->second->getAddress())
1481         return overlapError(B, *I->second);
1482     }
1483 
1484     // If we're not at the start of the map, check for overlap with the previous
1485     // element.
1486     if (I != AddrToBlock.begin()) {
1487       auto &PrevBlock = *std::prev(I)->second;
1488       if (PrevBlock.getAddress() + PrevBlock.getSize() > B.getAddress())
1489         return overlapError(B, PrevBlock);
1490     }
1491 
1492     AddrToBlock.insert(I, std::make_pair(B.getAddress(), &B));
1493     return Error::success();
1494   }
1495 
1496   /// Add a block to the map without checking for overlap with existing blocks.
1497   /// The client is responsible for ensuring that the block added does not
1498   /// overlap with any existing block.
addBlockWithoutChecking(Block & B)1499   void addBlockWithoutChecking(Block &B) { AddrToBlock[B.getAddress()] = &B; }
1500 
1501   /// Add a range of blocks to the map. Returns an error if any block in the
1502   /// range overlaps with any other block in the range, or with any existing
1503   /// block in the map.
1504   template <typename BlockPtrRange,
1505             typename PredFn = decltype(includeAllBlocks)>
1506   Error addBlocks(BlockPtrRange &&Blocks, PredFn Pred = includeAllBlocks) {
1507     for (auto *B : Blocks)
1508       if (auto Err = addBlock(*B, Pred))
1509         return Err;
1510     return Error::success();
1511   }
1512 
1513   /// Add a range of blocks to the map without checking for overlap with
1514   /// existing blocks. The client is responsible for ensuring that the block
1515   /// added does not overlap with any existing block.
1516   template <typename BlockPtrRange>
addBlocksWithoutChecking(BlockPtrRange && Blocks)1517   void addBlocksWithoutChecking(BlockPtrRange &&Blocks) {
1518     for (auto *B : Blocks)
1519       addBlockWithoutChecking(*B);
1520   }
1521 
1522   /// Iterates over (Address, Block*) pairs in ascending order of address.
begin()1523   const_iterator begin() const { return AddrToBlock.begin(); }
end()1524   const_iterator end() const { return AddrToBlock.end(); }
1525 
1526   /// Returns the block starting at the given address, or nullptr if no such
1527   /// block exists.
getBlockAt(orc::ExecutorAddr Addr)1528   Block *getBlockAt(orc::ExecutorAddr Addr) const {
1529     auto I = AddrToBlock.find(Addr);
1530     if (I == AddrToBlock.end())
1531       return nullptr;
1532     return I->second;
1533   }
1534 
1535   /// Returns the block covering the given address, or nullptr if no such block
1536   /// exists.
getBlockCovering(orc::ExecutorAddr Addr)1537   Block *getBlockCovering(orc::ExecutorAddr Addr) const {
1538     auto I = AddrToBlock.upper_bound(Addr);
1539     if (I == AddrToBlock.begin())
1540       return nullptr;
1541     auto *B = std::prev(I)->second;
1542     if (Addr < B->getAddress() + B->getSize())
1543       return B;
1544     return nullptr;
1545   }
1546 
1547 private:
overlapError(Block & NewBlock,Block & ExistingBlock)1548   Error overlapError(Block &NewBlock, Block &ExistingBlock) {
1549     auto NewBlockEnd = NewBlock.getAddress() + NewBlock.getSize();
1550     auto ExistingBlockEnd =
1551         ExistingBlock.getAddress() + ExistingBlock.getSize();
1552     return make_error<JITLinkError>(
1553         "Block at " +
1554         formatv("{0:x16} -- {1:x16}", NewBlock.getAddress().getValue(),
1555                 NewBlockEnd.getValue()) +
1556         " overlaps " +
1557         formatv("{0:x16} -- {1:x16}", ExistingBlock.getAddress().getValue(),
1558                 ExistingBlockEnd.getValue()));
1559   }
1560 
1561   AddrToBlockMap AddrToBlock;
1562 };
1563 
1564 /// A map of addresses to Symbols.
1565 class SymbolAddressMap {
1566 public:
1567   using SymbolVector = SmallVector<Symbol *, 1>;
1568 
1569   /// Add a symbol to the SymbolAddressMap.
addSymbol(Symbol & Sym)1570   void addSymbol(Symbol &Sym) {
1571     AddrToSymbols[Sym.getAddress()].push_back(&Sym);
1572   }
1573 
1574   /// Add all symbols in a given range to the SymbolAddressMap.
1575   template <typename SymbolPtrCollection>
addSymbols(SymbolPtrCollection && Symbols)1576   void addSymbols(SymbolPtrCollection &&Symbols) {
1577     for (auto *Sym : Symbols)
1578       addSymbol(*Sym);
1579   }
1580 
1581   /// Returns the list of symbols that start at the given address, or nullptr if
1582   /// no such symbols exist.
getSymbolsAt(orc::ExecutorAddr Addr)1583   const SymbolVector *getSymbolsAt(orc::ExecutorAddr Addr) const {
1584     auto I = AddrToSymbols.find(Addr);
1585     if (I == AddrToSymbols.end())
1586       return nullptr;
1587     return &I->second;
1588   }
1589 
1590 private:
1591   std::map<orc::ExecutorAddr, SymbolVector> AddrToSymbols;
1592 };
1593 
1594 /// A function for mutating LinkGraphs.
1595 using LinkGraphPassFunction = std::function<Error(LinkGraph &)>;
1596 
1597 /// A list of LinkGraph passes.
1598 using LinkGraphPassList = std::vector<LinkGraphPassFunction>;
1599 
1600 /// An LinkGraph pass configuration, consisting of a list of pre-prune,
1601 /// post-prune, and post-fixup passes.
1602 struct PassConfiguration {
1603 
1604   /// Pre-prune passes.
1605   ///
1606   /// These passes are called on the graph after it is built, and before any
1607   /// symbols have been pruned. Graph nodes still have their original vmaddrs.
1608   ///
1609   /// Notable use cases: Marking symbols live or should-discard.
1610   LinkGraphPassList PrePrunePasses;
1611 
1612   /// Post-prune passes.
1613   ///
1614   /// These passes are called on the graph after dead stripping, but before
1615   /// memory is allocated or nodes assigned their final addresses.
1616   ///
1617   /// Notable use cases: Building GOT, stub, and TLV symbols.
1618   LinkGraphPassList PostPrunePasses;
1619 
1620   /// Post-allocation passes.
1621   ///
1622   /// These passes are called on the graph after memory has been allocated and
1623   /// defined nodes have been assigned their final addresses, but before the
1624   /// context has been notified of these addresses. At this point externals
1625   /// have not been resolved, and symbol content has not yet been copied into
1626   /// working memory.
1627   ///
1628   /// Notable use cases: Setting up data structures associated with addresses
1629   /// of defined symbols (e.g. a mapping of __dso_handle to JITDylib* for the
1630   /// JIT runtime) -- using a PostAllocationPass for this ensures that the
1631   /// data structures are in-place before any query for resolved symbols
1632   /// can complete.
1633   LinkGraphPassList PostAllocationPasses;
1634 
1635   /// Pre-fixup passes.
1636   ///
1637   /// These passes are called on the graph after memory has been allocated,
1638   /// content copied into working memory, and all nodes (including externals)
1639   /// have been assigned their final addresses, but before any fixups have been
1640   /// applied.
1641   ///
1642   /// Notable use cases: Late link-time optimizations like GOT and stub
1643   /// elimination.
1644   LinkGraphPassList PreFixupPasses;
1645 
1646   /// Post-fixup passes.
1647   ///
1648   /// These passes are called on the graph after block contents has been copied
1649   /// to working memory, and fixups applied. Blocks have been updated to point
1650   /// to their fixed up content.
1651   ///
1652   /// Notable use cases: Testing and validation.
1653   LinkGraphPassList PostFixupPasses;
1654 };
1655 
1656 /// Flags for symbol lookup.
1657 ///
1658 /// FIXME: These basically duplicate orc::SymbolLookupFlags -- We should merge
1659 ///        the two types once we have an OrcSupport library.
1660 enum class SymbolLookupFlags { RequiredSymbol, WeaklyReferencedSymbol };
1661 
1662 raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF);
1663 
1664 /// A map of symbol names to resolved addresses.
1665 using AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>;
1666 
1667 /// A function object to call with a resolved symbol map (See AsyncLookupResult)
1668 /// or an error if resolution failed.
1669 class JITLinkAsyncLookupContinuation {
1670 public:
1671   virtual ~JITLinkAsyncLookupContinuation() = default;
1672   virtual void run(Expected<AsyncLookupResult> LR) = 0;
1673 
1674 private:
1675   virtual void anchor();
1676 };
1677 
1678 /// Create a lookup continuation from a function object.
1679 template <typename Continuation>
1680 std::unique_ptr<JITLinkAsyncLookupContinuation>
createLookupContinuation(Continuation Cont)1681 createLookupContinuation(Continuation Cont) {
1682 
1683   class Impl final : public JITLinkAsyncLookupContinuation {
1684   public:
1685     Impl(Continuation C) : C(std::move(C)) {}
1686     void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); }
1687 
1688   private:
1689     Continuation C;
1690   };
1691 
1692   return std::make_unique<Impl>(std::move(Cont));
1693 }
1694 
1695 /// Holds context for a single jitLink invocation.
1696 class JITLinkContext {
1697 public:
1698   using LookupMap = DenseMap<StringRef, SymbolLookupFlags>;
1699 
1700   /// Create a JITLinkContext.
JITLinkContext(const JITLinkDylib * JD)1701   JITLinkContext(const JITLinkDylib *JD) : JD(JD) {}
1702 
1703   /// Destroy a JITLinkContext.
1704   virtual ~JITLinkContext();
1705 
1706   /// Return the JITLinkDylib that this link is targeting, if any.
getJITLinkDylib()1707   const JITLinkDylib *getJITLinkDylib() const { return JD; }
1708 
1709   /// Return the MemoryManager to be used for this link.
1710   virtual JITLinkMemoryManager &getMemoryManager() = 0;
1711 
1712   /// Notify this context that linking failed.
1713   /// Called by JITLink if linking cannot be completed.
1714   virtual void notifyFailed(Error Err) = 0;
1715 
1716   /// Called by JITLink to resolve external symbols. This method is passed a
1717   /// lookup continutation which it must call with a result to continue the
1718   /// linking process.
1719   virtual void lookup(const LookupMap &Symbols,
1720                       std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0;
1721 
1722   /// Called by JITLink once all defined symbols in the graph have been assigned
1723   /// their final memory locations in the target process. At this point the
1724   /// LinkGraph can be inspected to build a symbol table, however the block
1725   /// content will not generally have been copied to the target location yet.
1726   ///
1727   /// If the client detects an error in the LinkGraph state (e.g. unexpected or
1728   /// missing symbols) they may return an error here. The error will be
1729   /// propagated to notifyFailed and the linker will bail out.
1730   virtual Error notifyResolved(LinkGraph &G) = 0;
1731 
1732   /// Called by JITLink to notify the context that the object has been
1733   /// finalized (i.e. emitted to memory and memory permissions set). If all of
1734   /// this objects dependencies have also been finalized then the code is ready
1735   /// to run.
1736   virtual void notifyFinalized(JITLinkMemoryManager::FinalizedAlloc Alloc) = 0;
1737 
1738   /// Called by JITLink prior to linking to determine whether default passes for
1739   /// the target should be added. The default implementation returns true.
1740   /// If subclasses override this method to return false for any target then
1741   /// they are required to fully configure the pass pipeline for that target.
1742   virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;
1743 
1744   /// Returns the mark-live pass to be used for this link. If no pass is
1745   /// returned (the default) then the target-specific linker implementation will
1746   /// choose a conservative default (usually marking all symbols live).
1747   /// This function is only called if shouldAddDefaultTargetPasses returns true,
1748   /// otherwise the JITContext is responsible for adding a mark-live pass in
1749   /// modifyPassConfig.
1750   virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const;
1751 
1752   /// Called by JITLink to modify the pass pipeline prior to linking.
1753   /// The default version performs no modification.
1754   virtual Error modifyPassConfig(LinkGraph &G, PassConfiguration &Config);
1755 
1756 private:
1757   const JITLinkDylib *JD = nullptr;
1758 };
1759 
1760 /// Marks all symbols in a graph live. This can be used as a default,
1761 /// conservative mark-live implementation.
1762 Error markAllSymbolsLive(LinkGraph &G);
1763 
1764 /// Create an out of range error for the given edge in the given block.
1765 Error makeTargetOutOfRangeError(const LinkGraph &G, const Block &B,
1766                                 const Edge &E);
1767 
1768 Error makeAlignmentError(llvm::orc::ExecutorAddr Loc, uint64_t Value, int N,
1769                          const Edge &E);
1770 
1771 /// Base case for edge-visitors where the visitor-list is empty.
visitEdge(LinkGraph & G,Block * B,Edge & E)1772 inline void visitEdge(LinkGraph &G, Block *B, Edge &E) {}
1773 
1774 /// Applies the first visitor in the list to the given edge. If the visitor's
1775 /// visitEdge method returns true then we return immediately, otherwise we
1776 /// apply the next visitor.
1777 template <typename VisitorT, typename... VisitorTs>
visitEdge(LinkGraph & G,Block * B,Edge & E,VisitorT && V,VisitorTs &&...Vs)1778 void visitEdge(LinkGraph &G, Block *B, Edge &E, VisitorT &&V,
1779                VisitorTs &&...Vs) {
1780   if (!V.visitEdge(G, B, E))
1781     visitEdge(G, B, E, std::forward<VisitorTs>(Vs)...);
1782 }
1783 
1784 /// For each edge in the given graph, apply a list of visitors to the edge,
1785 /// stopping when the first visitor's visitEdge method returns true.
1786 ///
1787 /// Only visits edges that were in the graph at call time: if any visitor
1788 /// adds new edges those will not be visited. Visitors are not allowed to
1789 /// remove edges (though they can change their kind, target, and addend).
1790 template <typename... VisitorTs>
visitExistingEdges(LinkGraph & G,VisitorTs &&...Vs)1791 void visitExistingEdges(LinkGraph &G, VisitorTs &&...Vs) {
1792   // We may add new blocks during this process, but we don't want to iterate
1793   // over them, so build a worklist.
1794   std::vector<Block *> Worklist(G.blocks().begin(), G.blocks().end());
1795 
1796   for (auto *B : Worklist)
1797     for (auto &E : B->edges())
1798       visitEdge(G, B, E, std::forward<VisitorTs>(Vs)...);
1799 }
1800 
1801 /// Create a LinkGraph from the given object buffer.
1802 ///
1803 /// Note: The graph does not take ownership of the underlying buffer, nor copy
1804 /// its contents. The caller is responsible for ensuring that the object buffer
1805 /// outlives the graph.
1806 Expected<std::unique_ptr<LinkGraph>>
1807 createLinkGraphFromObject(MemoryBufferRef ObjectBuffer);
1808 
1809 /// Link the given graph.
1810 void link(std::unique_ptr<LinkGraph> G, std::unique_ptr<JITLinkContext> Ctx);
1811 
1812 } // end namespace jitlink
1813 } // end namespace llvm
1814 
1815 #endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
1816