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