include/llvm/ExecutionEngine/JITLink/JITLink.h

   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/Triple.h"
  21 #include "llvm/ExecutionEngine/JITSymbol.h"
  22 #include "llvm/Support/Allocator.h"
  23 #include "llvm/Support/Endian.h"
  24 #include "llvm/Support/Error.h"
  25 #include "llvm/Support/FormatVariadic.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/Support/Memory.h"
  28 #include "llvm/Support/MemoryBuffer.h"
  29
  30 #include <map>
  31 #include <string>
  32 #include <system_error>
  33
  34 namespace llvm {
  35 namespace jitlink {
  36
  37 class Symbol;
  38 class Section;
  39
  40 /// Base class for errors originating in JIT linker, e.g. missing relocation
  41 /// support.
  42 class JITLinkError : public ErrorInfo<JITLinkError> {
  43 public:
  44   static char ID;
  45
  46   JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}
  47
  48   void log(raw_ostream &OS) const override;
  49   const std::string &getErrorMessage() const { return ErrMsg; }
  50   std::error_code convertToErrorCode() const override;
  51
  52 private:
  53   std::string ErrMsg;
  54 };
  55
  56 /// Represents fixups and constraints in the LinkGraph.
  57 class Edge {
  58 public:
  59   using Kind = uint8_t;
  60
  61   enum GenericEdgeKind : Kind {
  62     Invalid,                    // Invalid edge value.
  63     FirstKeepAlive,             // Keeps target alive. Offset/addend zero.
  64     KeepAlive = FirstKeepAlive, // Tag first edge kind that preserves liveness.
  65     FirstRelocation             // First architecture specific relocation.
  66   };
  67
  68   using OffsetT = uint32_t;
  69   using AddendT = int64_t;
  70
  71   Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
  72       : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
  73
  74   OffsetT getOffset() const { return Offset; }
  75   Kind getKind() const { return K; }
  76   void setKind(Kind K) { this->K = K; }
  77   bool isRelocation() const { return K >= FirstRelocation; }
  78   Kind getRelocation() const {
  79     assert(isRelocation() && "Not a relocation edge");
  80     return K - FirstRelocation;
  81   }
  82   bool isKeepAlive() const { return K >= FirstKeepAlive; }
  83   Symbol &getTarget() const { return *Target; }
  84   void setTarget(Symbol &Target) { this->Target = &Target; }
  85   AddendT getAddend() const { return Addend; }
  86   void setAddend(AddendT Addend) { this->Addend = Addend; }
  87
  88 private:
  89   Symbol *Target = nullptr;
  90   OffsetT Offset = 0;
  91   AddendT Addend = 0;
  92   Kind K = 0;
  93 };
  94
  95 /// Returns the string name of the given generic edge kind, or "unknown"
  96 /// otherwise. Useful for debugging.
  97 const char *getGenericEdgeKindName(Edge::Kind K);
  98
  99 /// Base class for Addressable entities (externals, absolutes, blocks).
 100 class Addressable {
 101   friend class LinkGraph;
 102
 103 protected:
 104   Addressable(JITTargetAddress Address, bool IsDefined)
 105       : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {}
 106
 107   Addressable(JITTargetAddress Address)
 108       : Address(Address), IsDefined(false), IsAbsolute(true) {
 109     assert(!(IsDefined && IsAbsolute) &&
 110            "Block cannot be both defined and absolute");
 111   }
 112
 113 public:
 114   Addressable(const Addressable &) = delete;
 115   Addressable &operator=(const Addressable &) = default;
 116   Addressable(Addressable &&) = delete;
 117   Addressable &operator=(Addressable &&) = default;
 118
 119   JITTargetAddress getAddress() const { return Address; }
 120   void setAddress(JITTargetAddress Address) { this->Address = Address; }
 121
 122   /// Returns true if this is a defined addressable, in which case you
 123   /// can downcast this to a .
 124   bool isDefined() const { return static_cast<bool>(IsDefined); }
 125   bool isAbsolute() const { return static_cast<bool>(IsAbsolute); }
 126
 127 private:
 128   JITTargetAddress Address = 0;
 129   uint64_t IsDefined : 1;
 130   uint64_t IsAbsolute : 1;
 131 };
 132
 133 using BlockOrdinal = unsigned;
 134 using SectionOrdinal = unsigned;
 135
 136 /// An Addressable with content and edges.
 137 class Block : public Addressable {
 138   friend class LinkGraph;
 139
 140 private:
 141   /// Create a zero-fill defined addressable.
 142   Block(Section &Parent, BlockOrdinal Ordinal, JITTargetAddress Size,
 143         JITTargetAddress Address, uint64_t Alignment, uint64_t AlignmentOffset)
 144       : Addressable(Address, true), Parent(Parent), Size(Size),
 145         Ordinal(Ordinal) {
 146     assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
 147     assert(AlignmentOffset < Alignment &&
 148            "Alignment offset cannot exceed alignment");
 149     assert(AlignmentOffset <= MaxAlignmentOffset &&
 150            "Alignment offset exceeds maximum");
 151     P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
 152     this->AlignmentOffset = AlignmentOffset;
 153   }
 154
 155   /// Create a defined addressable for the given content.
 156   Block(Section &Parent, BlockOrdinal Ordinal, StringRef Content,
 157         JITTargetAddress Address, uint64_t Alignment, uint64_t AlignmentOffset)
 158       : Addressable(Address, true), Parent(Parent), Data(Content.data()),
 159         Size(Content.size()), Ordinal(Ordinal) {
 160     assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2");
 161     assert(AlignmentOffset < Alignment &&
 162            "Alignment offset cannot exceed alignment");
 163     assert(AlignmentOffset <= MaxAlignmentOffset &&
 164            "Alignment offset exceeds maximum");
 165     P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
 166     this->AlignmentOffset = AlignmentOffset;
 167   }
 168
 169 public:
 170   using EdgeVector = std::vector<Edge>;
 171   using edge_iterator = EdgeVector::iterator;
 172   using const_edge_iterator = EdgeVector::const_iterator;
 173
 174   Block(const Block &) = delete;
 175   Block &operator=(const Block &) = delete;
 176   Block(Block &&) = delete;
 177   Block &operator=(Block &&) = delete;
 178
 179   /// Return the parent section for this block.
 180   Section &getSection() const { return Parent; }
 181
 182   /// Return the ordinal for this block.
 183   BlockOrdinal getOrdinal() const { return Ordinal; }
 184
 185   /// Returns true if this is a zero-fill block.
 186   ///
 187   /// If true, getSize is callable but getContent is not (the content is
 188   /// defined to be a sequence of zero bytes of length Size).
 189   bool isZeroFill() const { return !Data; }
 190
 191   /// Returns the size of this defined addressable.
 192   size_t getSize() const { return Size; }
 193
 194   /// Get the content for this block. Block must not be a zero-fill block.
 195   StringRef getContent() const {
 196     assert(Data && "Section does not contain content");
 197     return StringRef(Data, Size);
 198   }
 199
 200   /// Set the content for this block.
 201   /// Caller is responsible for ensuring the underlying bytes are not
 202   /// deallocated while pointed to by this block.
 203   void setContent(StringRef Content) {
 204     Data = Content.data();
 205     Size = Content.size();
 206   }
 207
 208   /// Get the alignment for this content.
 209   uint64_t getAlignment() const { return 1ull << P2Align; }
 210
 211   /// Get the alignment offset for this content.
 212   uint64_t getAlignmentOffset() const { return AlignmentOffset; }
 213
 214   /// Add an edge to this block.
 215   void addEdge(Edge::Kind K, Edge::OffsetT Offset, Symbol &Target,
 216                Edge::AddendT Addend) {
 217     Edges.push_back(Edge(K, Offset, Target, Addend));
 218   }
 219
 220   /// Return the list of edges attached to this content.
 221   iterator_range<edge_iterator> edges() {
 222     return make_range(Edges.begin(), Edges.end());
 223   }
 224
 225   /// Returns the list of edges attached to this content.
 226   iterator_range<const_edge_iterator> edges() const {
 227     return make_range(Edges.begin(), Edges.end());
 228   }
 229
 230   /// Return the size of the edges list.
 231   size_t edges_size() const { return Edges.size(); }
 232
 233   /// Returns true if the list of edges is empty.
 234   bool edges_empty() const { return Edges.empty(); }
 235
 236 private:
 237   static constexpr uint64_t MaxAlignmentOffset = (1ULL << 57) - 1;
 238
 239   uint64_t P2Align : 5;
 240   uint64_t AlignmentOffset : 57;
 241   Section &Parent;
 242   const char *Data = nullptr;
 243   size_t Size = 0;
 244   BlockOrdinal Ordinal = 0;
 245   std::vector<Edge> Edges;
 246 };
 247
 248 /// Describes symbol linkage. This can be used to make resolve definition
 249 /// clashes.
 250 enum class Linkage : uint8_t {
 251   Strong,
 252   Weak,
 253 };
 254
 255 /// For errors and debugging output.
 256 const char *getLinkageName(Linkage L);
 257
 258 /// Defines the scope in which this symbol should be visible:
 259 ///   Default -- Visible in the public interface of the linkage unit.
 260 ///   Hidden -- Visible within the linkage unit, but not exported from it.
 261 ///   Local -- Visible only within the LinkGraph.
 262 enum class Scope : uint8_t { Default, Hidden, Local };
 263
 264 /// For debugging output.
 265 const char *getScopeName(Scope S);
 266
 267 raw_ostream &operator<<(raw_ostream &OS, const Block &B);
 268
 269 /// Symbol representation.
 270 ///
 271 /// Symbols represent locations within Addressable objects.
 272 /// They can be either Named or Anonymous.
 273 /// Anonymous symbols have neither linkage nor visibility, and must point at
 274 /// ContentBlocks.
 275 /// Named symbols may be in one of four states:
 276 ///   - Null: Default initialized. Assignable, but otherwise unusable.
 277 ///   - Defined: Has both linkage and visibility and points to a ContentBlock
 278 ///   - Common: Has both linkage and visibility, points to a null Addressable.
 279 ///   - External: Has neither linkage nor visibility, points to an external
 280 ///     Addressable.
 281 ///
 282 class Symbol {
 283   friend class LinkGraph;
 284
 285 private:
 286   Symbol(Addressable &Base, JITTargetAddress Offset, StringRef Name,
 287          JITTargetAddress Size, Linkage L, Scope S, bool IsLive,
 288          bool IsCallable)
 289       : Name(Name), Base(&Base), Offset(Offset), Size(Size) {
 290     setLinkage(L);
 291     setScope(S);
 292     setLive(IsLive);
 293     setCallable(IsCallable);
 294   }
 295
 296   static Symbol &constructCommon(void *SymStorage, Block &Base, StringRef Name,
 297                                  JITTargetAddress Size, Scope S, bool IsLive) {
 298     assert(SymStorage && "Storage cannot be null");
 299     assert(!Name.empty() && "Common symbol name cannot be empty");
 300     assert(Base.isDefined() &&
 301            "Cannot create common symbol from undefined block");
 302     assert(static_cast<Block &>(Base).getSize() == Size &&
 303            "Common symbol size should match underlying block size");
 304     auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
 305     new (Sym) Symbol(Base, 0, Name, Size, Linkage::Weak, S, IsLive, false);
 306     return *Sym;
 307   }
 308
 309   static Symbol &constructExternal(void *SymStorage, Addressable &Base,
 310                                    StringRef Name, JITTargetAddress Size) {
 311     assert(SymStorage && "Storage cannot be null");
 312     assert(!Base.isDefined() &&
 313            "Cannot create external symbol from defined block");
 314     assert(!Name.empty() && "External symbol name cannot be empty");
 315     auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
 316     new (Sym) Symbol(Base, 0, Name, Size, Linkage::Strong, Scope::Default,
 317                      false, false);
 318     return *Sym;
 319   }
 320
 321   static Symbol &constructAbsolute(void *SymStorage, Addressable &Base,
 322                                    StringRef Name, JITTargetAddress Size,
 323                                    Linkage L, Scope S, bool IsLive) {
 324     assert(SymStorage && "Storage cannot be null");
 325     assert(!Base.isDefined() &&
 326            "Cannot create absolute symbol from a defined block");
 327     auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
 328     new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
 329     return *Sym;
 330   }
 331
 332   static Symbol &constructAnonDef(void *SymStorage, Block &Base,
 333                                   JITTargetAddress Offset,
 334                                   JITTargetAddress Size, bool IsCallable,
 335                                   bool IsLive) {
 336     assert(SymStorage && "Storage cannot be null");
 337     auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
 338     new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
 339                      Scope::Local, IsLive, IsCallable);
 340     return *Sym;
 341   }
 342
 343   static Symbol &constructNamedDef(void *SymStorage, Block &Base,
 344                                    JITTargetAddress Offset, StringRef Name,
 345                                    JITTargetAddress Size, Linkage L, Scope S,
 346                                    bool IsLive, bool IsCallable) {
 347     assert(SymStorage && "Storage cannot be null");
 348     assert(!Name.empty() && "Name cannot be empty");
 349     auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
 350     new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
 351     return *Sym;
 352   }
 353
 354 public:
 355   /// Create a null Symbol. This allows Symbols to be default initialized for
 356   /// use in containers (e.g. as map values). Null symbols are only useful for
 357   /// assigning to.
 358   Symbol() = default;
 359
 360   // Symbols are not movable or copyable.
 361   Symbol(const Symbol &) = delete;
 362   Symbol &operator=(const Symbol &) = delete;
 363   Symbol(Symbol &&) = delete;
 364   Symbol &operator=(Symbol &&) = delete;
 365
 366   /// Returns true if this symbol has a name.
 367   bool hasName() const { return !Name.empty(); }
 368
 369   /// Returns the name of this symbol (empty if the symbol is anonymous).
 370   StringRef getName() const {
 371     assert((!Name.empty() || getScope() == Scope::Local) &&
 372            "Anonymous symbol has non-local scope");
 373     return Name;
 374   }
 375
 376   /// Returns true if this Symbol has content (potentially) defined within this
 377   /// object file (i.e. is anything but an external or absolute symbol).
 378   bool isDefined() const {
 379     assert(Base && "Attempt to access null symbol");
 380     return Base->isDefined();
 381   }
 382
 383   /// Returns true if this symbol is live (i.e. should be treated as a root for
 384   /// dead stripping).
 385   bool isLive() const {
 386     assert(Base && "Attempting to access null symbol");
 387     return IsLive;
 388   }
 389
 390   /// Set this symbol's live bit.
 391   void setLive(bool IsLive) { this->IsLive = IsLive; }
 392
 393   /// Returns true is this symbol is callable.
 394   bool isCallable() const { return IsCallable; }
 395
 396   /// Set this symbol's callable bit.
 397   void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }
 398
 399   /// Returns true if the underlying addressable is an unresolved external.
 400   bool isExternal() const {
 401     assert(Base && "Attempt to access null symbol");
 402     return !Base->isDefined() && !Base->isAbsolute();
 403   }
 404
 405   /// Returns true if the underlying addressable is an absolute symbol.
 406   bool isAbsolute() const {
 407     assert(Base && "Attempt to access null symbol");
 408     return !Base->isDefined() && Base->isAbsolute();
 409   }
 410
 411   /// Return the addressable that this symbol points to.
 412   Addressable &getAddressable() {
 413     assert(Base && "Cannot get underlying addressable for null symbol");
 414     return *Base;
 415   }
 416
 417   /// Return the addressable that thsi symbol points to.
 418   const Addressable &getAddressable() const {
 419     assert(Base && "Cannot get underlying addressable for null symbol");
 420     return *Base;
 421   }
 422
 423   /// Return the Block for this Symbol (Symbol must be defined).
 424   Block &getBlock() {
 425     assert(Base && "Cannot get block for null symbol");
 426     assert(Base->isDefined() && "Not a defined symbol");
 427     return static_cast<Block &>(*Base);
 428   }
 429
 430   /// Return the Block for this Symbol (Symbol must be defined).
 431   const Block &getBlock() const {
 432     assert(Base && "Cannot get block for null symbol");
 433     assert(Base->isDefined() && "Not a defined symbol");
 434     return static_cast<const Block &>(*Base);
 435   }
 436
 437   /// Returns the offset for this symbol within the underlying addressable.
 438   JITTargetAddress getOffset() const { return Offset; }
 439
 440   /// Returns the address of this symbol.
 441   JITTargetAddress getAddress() const { return Base->getAddress() + Offset; }
 442
 443   /// Returns the size of this symbol.
 444   JITTargetAddress getSize() const { return Size; }
 445
 446   /// Returns true if this symbol is backed by a zero-fill block.
 447   /// This method may only be called on defined symbols.
 448   bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }
 449
 450   /// Returns the content in the underlying block covered by this symbol.
 451   /// This method may only be called on defined non-zero-fill symbols.
 452   StringRef getSymbolContent() const {
 453     return getBlock().getContent().substr(Offset, Size);
 454   }
 455
 456   /// Get the linkage for this Symbol.
 457   Linkage getLinkage() const { return static_cast<Linkage>(L); }
 458
 459   /// Set the linkage for this Symbol.
 460   void setLinkage(Linkage L) {
 461     assert((L == Linkage::Strong || (Base->isDefined() && !Name.empty())) &&
 462            "Linkage can only be applied to defined named symbols");
 463     this->L = static_cast<uint8_t>(L);
 464   }
 465
 466   /// Get the visibility for this Symbol.
 467   Scope getScope() const { return static_cast<Scope>(S); }
 468
 469   /// Set the visibility for this Symbol.
 470   void setScope(Scope S) {
 471     assert((S == Scope::Default || Base->isDefined() || Base->isAbsolute()) &&
 472            "Invalid visibility for symbol type");
 473     this->S = static_cast<uint8_t>(S);
 474   }
 475
 476 private:
 477   void makeExternal(Addressable &A) {
 478     assert(!A.isDefined() && "Attempting to make external with defined block");
 479     Base = &A;
 480     Offset = 0;
 481     setLinkage(Linkage::Strong);
 482     setScope(Scope::Default);
 483     IsLive = 0;
 484     // note: Size and IsCallable fields left unchanged.
 485   }
 486
 487   static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
 488
 489   // FIXME: A char* or SymbolStringPtr may pack better.
 490   StringRef Name;
 491   Addressable *Base = nullptr;
 492   uint64_t Offset : 59;
 493   uint64_t L : 1;
 494   uint64_t S : 2;
 495   uint64_t IsLive : 1;
 496   uint64_t IsCallable : 1;
 497   JITTargetAddress Size = 0;
 498 };
 499
 500 raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);
 501
 502 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
 503                StringRef EdgeKindName);
 504
 505 /// Represents an object file section.
 506 class Section {
 507   friend class LinkGraph;
 508
 509 private:
 510   Section(StringRef Name, sys::Memory::ProtectionFlags Prot,
 511           SectionOrdinal SecOrdinal)
 512       : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {}
 513
 514   using SymbolSet = DenseSet<Symbol *>;
 515   using BlockSet = DenseSet<Block *>;
 516
 517 public:
 518   using symbol_iterator = SymbolSet::iterator;
 519   using const_symbol_iterator = SymbolSet::const_iterator;
 520
 521   using block_iterator = BlockSet::iterator;
 522   using const_block_iterator = BlockSet::const_iterator;
 523
 524   ~Section();
 525
 526   /// Returns the name of this section.
 527   StringRef getName() const { return Name; }
 528
 529   /// Returns the protection flags for this section.
 530   sys::Memory::ProtectionFlags getProtectionFlags() const { return Prot; }
 531
 532   /// Returns the ordinal for this section.
 533   SectionOrdinal getOrdinal() const { return SecOrdinal; }
 534
 535   /// Returns an iterator over the symbols defined in this section.
 536   iterator_range<symbol_iterator> symbols() {
 537     return make_range(Symbols.begin(), Symbols.end());
 538   }
 539
 540   /// Returns an iterator over the symbols defined in this section.
 541   iterator_range<const_symbol_iterator> symbols() const {
 542     return make_range(Symbols.begin(), Symbols.end());
 543   }
 544
 545   /// Return the number of symbols in this section.
 546   SymbolSet::size_type symbols_size() { return Symbols.size(); }
 547
 548   /// Return true if this section contains no symbols.
 549   bool symbols_empty() const { return Symbols.empty(); }
 550
 551   /// Returns the ordinal for the next block.
 552   BlockOrdinal getNextBlockOrdinal() { return NextBlockOrdinal++; }
 553
 554 private:
 555   void addSymbol(Symbol &Sym) {
 556     assert(!Symbols.count(&Sym) && "Symbol is already in this section");
 557     Symbols.insert(&Sym);
 558   }
 559
 560   void removeSymbol(Symbol &Sym) {
 561     assert(Symbols.count(&Sym) && "symbol is not in this section");
 562     Symbols.erase(&Sym);
 563   }
 564
 565   StringRef Name;
 566   sys::Memory::ProtectionFlags Prot;
 567   SectionOrdinal SecOrdinal = 0;
 568   BlockOrdinal NextBlockOrdinal = 0;
 569   SymbolSet Symbols;
 570 };
 571
 572 /// Represents a section address range via a pair of Block pointers
 573 /// to the first and last Blocks in the section.
 574 class SectionRange {
 575 public:
 576   SectionRange() = default;
 577   SectionRange(const Section &Sec) {
 578     if (Sec.symbols_empty())
 579       return;
 580     First = Last = *Sec.symbols().begin();
 581     for (auto *Sym : Sec.symbols()) {
 582       if (Sym->getAddress() < First->getAddress())
 583         First = Sym;
 584       if (Sym->getAddress() > Last->getAddress())
 585         Last = Sym;
 586     }
 587   }
 588   Symbol *getFirstSymbol() const {
 589     assert((!Last || First) && "First can not be null if end is non-null");
 590     return First;
 591   }
 592   Symbol *getLastSymbol() const {
 593     assert((First || !Last) && "Last can not be null if start is non-null");
 594     return Last;
 595   }
 596   bool isEmpty() const {
 597     assert((First || !Last) && "Last can not be null if start is non-null");
 598     return !First;
 599   }
 600   JITTargetAddress getStart() const {
 601     return First ? First->getBlock().getAddress() : 0;
 602   }
 603   JITTargetAddress getEnd() const {
 604     return Last ? Last->getBlock().getAddress() + Last->getBlock().getSize()
 605                 : 0;
 606   }
 607   uint64_t getSize() const { return getEnd() - getStart(); }
 608
 609 private:
 610   Symbol *First = nullptr;
 611   Symbol *Last = nullptr;
 612 };
 613
 614 class LinkGraph {
 615 private:
 616   using SectionList = std::vector<std::unique_ptr<Section>>;
 617   using ExternalSymbolSet = DenseSet<Symbol *>;
 618   using BlockSet = DenseSet<Block *>;
 619
 620   template <typename... ArgTs>
 621   Addressable &createAddressable(ArgTs &&... Args) {
 622     Addressable *A =
 623         reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
 624     new (A) Addressable(std::forward<ArgTs>(Args)...);
 625     return *A;
 626   }
 627
 628   void destroyAddressable(Addressable &A) {
 629     A.~Addressable();
 630     Allocator.Deallocate(&A);
 631   }
 632
 633   template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) {
 634     Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>());
 635     new (B) Block(std::forward<ArgTs>(Args)...);
 636     Blocks.insert(B);
 637     return *B;
 638   }
 639
 640   void destroyBlock(Block &B) {
 641     Blocks.erase(&B);
 642     B.~Block();
 643     Allocator.Deallocate(&B);
 644   }
 645
 646   void destroySymbol(Symbol &S) {
 647     S.~Symbol();
 648     Allocator.Deallocate(&S);
 649   }
 650
 651 public:
 652   using external_symbol_iterator = ExternalSymbolSet::iterator;
 653
 654   using block_iterator = BlockSet::iterator;
 655
 656   using section_iterator = pointee_iterator<SectionList::iterator>;
 657   using const_section_iterator = pointee_iterator<SectionList::const_iterator>;
 658
 659   template <typename SectionItrT, typename SymbolItrT, typename T>
 660   class defined_symbol_iterator_impl
 661       : public iterator_facade_base<
 662             defined_symbol_iterator_impl<SectionItrT, SymbolItrT, T>,
 663             std::forward_iterator_tag, T> {
 664   public:
 665     defined_symbol_iterator_impl() = default;
 666
 667     defined_symbol_iterator_impl(SectionItrT SecI, SectionItrT SecE)
 668         : SecI(SecI), SecE(SecE),
 669           SymI(SecI != SecE ? SecI->symbols().begin() : SymbolItrT()) {
 670       moveToNextSymbolOrEnd();
 671     }
 672
 673     bool operator==(const defined_symbol_iterator_impl &RHS) const {
 674       return (SecI == RHS.SecI) && (SymI == RHS.SymI);
 675     }
 676
 677     T operator*() const {
 678       assert(SymI != SecI->symbols().end() && "Dereferencing end?");
 679       return *SymI;
 680     }
 681
 682     defined_symbol_iterator_impl operator++() {
 683       ++SymI;
 684       moveToNextSymbolOrEnd();
 685       return *this;
 686     }
 687
 688   private:
 689     void moveToNextSymbolOrEnd() {
 690       while (SecI != SecE && SymI == SecI->symbols().end()) {
 691         ++SecI;
 692         SymI = SecI == SecE ? SymbolItrT() : SecI->symbols().begin();
 693       }
 694     }
 695
 696     SectionItrT SecI, SecE;
 697     SymbolItrT SymI;
 698   };
 699
 700   using defined_symbol_iterator =
 701       defined_symbol_iterator_impl<const_section_iterator,
 702                                    Section::symbol_iterator, Symbol *>;
 703
 704   using const_defined_symbol_iterator = defined_symbol_iterator_impl<
 705       const_section_iterator, Section::const_symbol_iterator, const Symbol *>;
 706
 707   LinkGraph(std::string Name, unsigned PointerSize,
 708             support::endianness Endianness)
 709       : Name(std::move(Name)), PointerSize(PointerSize),
 710         Endianness(Endianness) {}
 711
 712   ~LinkGraph();
 713
 714   /// Returns the name of this graph (usually the name of the original
 715   /// underlying MemoryBuffer).
 716   const std::string &getName() { return Name; }
 717
 718   /// Returns the pointer size for use in this graph.
 719   unsigned getPointerSize() const { return PointerSize; }
 720
 721   /// Returns the endianness of content in this graph.
 722   support::endianness getEndianness() const { return Endianness; }
 723
 724   /// Create a section with the given name, protection flags, and alignment.
 725   Section &createSection(StringRef Name, sys::Memory::ProtectionFlags Prot) {
 726     std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size()));
 727     Sections.push_back(std::move(Sec));
 728     return *Sections.back();
 729   }
 730
 731   /// Create a content block.
 732   Block &createContentBlock(Section &Parent, StringRef Content,
 733                             uint64_t Address, uint64_t Alignment,
 734                             uint64_t AlignmentOffset) {
 735     return createBlock(Parent, Parent.getNextBlockOrdinal(), Content, Address,
 736                        Alignment, AlignmentOffset);
 737   }
 738
 739   /// Create a zero-fill block.
 740   Block &createZeroFillBlock(Section &Parent, uint64_t Size, uint64_t Address,
 741                              uint64_t Alignment, uint64_t AlignmentOffset) {
 742     return createBlock(Parent, Parent.getNextBlockOrdinal(), Size, Address,
 743                        Alignment, AlignmentOffset);
 744   }
 745
 746   /// Add an external symbol.
 747   /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
 748   /// size is not known, you should substitute '0'.
 749   Symbol &addExternalSymbol(StringRef Name, uint64_t Size) {
 750     auto &Sym = Symbol::constructExternal(
 751         Allocator.Allocate<Symbol>(), createAddressable(0, false), Name, Size);
 752     ExternalSymbols.insert(&Sym);
 753     return Sym;
 754   }
 755
 756   /// Add an absolute symbol.
 757   Symbol &addAbsoluteSymbol(StringRef Name, JITTargetAddress Address,
 758                             uint64_t Size, Linkage L, Scope S, bool IsLive) {
 759     auto &Sym = Symbol::constructAbsolute(Allocator.Allocate<Symbol>(),
 760                                           createAddressable(Address), Name,
 761                                           Size, L, S, IsLive);
 762     AbsoluteSymbols.insert(&Sym);
 763     return Sym;
 764   }
 765
 766   /// Convenience method for adding a weak zero-fill symbol.
 767   Symbol &addCommonSymbol(StringRef Name, Scope S, Section &Section,
 768                           JITTargetAddress Address, uint64_t Size,
 769                           uint64_t Alignment, bool IsLive) {
 770     auto &Sym = Symbol::constructCommon(
 771         Allocator.Allocate<Symbol>(),
 772         createBlock(Section, Section.getNextBlockOrdinal(), Address, Size,
 773                     Alignment, 0),
 774         Name, Size, S, IsLive);
 775     Section.addSymbol(Sym);
 776     return Sym;
 777   }
 778
 779   /// Add an anonymous symbol.
 780   Symbol &addAnonymousSymbol(Block &Content, JITTargetAddress Offset,
 781                              JITTargetAddress Size, bool IsCallable,
 782                              bool IsLive) {
 783     auto &Sym = Symbol::constructAnonDef(Allocator.Allocate<Symbol>(), Content,
 784                                          Offset, Size, IsCallable, IsLive);
 785     Content.getSection().addSymbol(Sym);
 786     return Sym;
 787   }
 788
 789   /// Add a named symbol.
 790   Symbol &addDefinedSymbol(Block &Content, JITTargetAddress Offset,
 791                            StringRef Name, JITTargetAddress Size, Linkage L,
 792                            Scope S, bool IsCallable, bool IsLive) {
 793     auto &Sym =
 794         Symbol::constructNamedDef(Allocator.Allocate<Symbol>(), Content, Offset,
 795                                   Name, Size, L, S, IsLive, IsCallable);
 796     Content.getSection().addSymbol(Sym);
 797     return Sym;
 798   }
 799
 800   iterator_range<section_iterator> sections() {
 801     return make_range(section_iterator(Sections.begin()),
 802                       section_iterator(Sections.end()));
 803   }
 804
 805   /// Returns the section with the given name if it exists, otherwise returns
 806   /// null.
 807   Section *findSectionByName(StringRef Name) {
 808     for (auto &S : sections())
 809       if (S.getName() == Name)
 810         return &S;
 811     return nullptr;
 812   }
 813
 814   iterator_range<external_symbol_iterator> external_symbols() {
 815     return make_range(ExternalSymbols.begin(), ExternalSymbols.end());
 816   }
 817
 818   iterator_range<external_symbol_iterator> absolute_symbols() {
 819     return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
 820   }
 821
 822   iterator_range<defined_symbol_iterator> defined_symbols() {
 823     return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()),
 824                       defined_symbol_iterator(Sections.end(), Sections.end()));
 825   }
 826
 827   iterator_range<const_defined_symbol_iterator> defined_symbols() const {
 828     return make_range(
 829         const_defined_symbol_iterator(Sections.begin(), Sections.end()),
 830         const_defined_symbol_iterator(Sections.end(), Sections.end()));
 831   }
 832
 833   iterator_range<block_iterator> blocks() {
 834     return make_range(Blocks.begin(), Blocks.end());
 835   }
 836
 837   /// Turn a defined symbol into an external one.
 838   void makeExternal(Symbol &Sym) {
 839     if (Sym.getAddressable().isAbsolute()) {
 840       assert(AbsoluteSymbols.count(&Sym) &&
 841              "Sym is not in the absolute symbols set");
 842       AbsoluteSymbols.erase(&Sym);
 843     } else {
 844       assert(Sym.isDefined() && "Sym is not a defined symbol");
 845       Section &Sec = Sym.getBlock().getSection();
 846       Sec.removeSymbol(Sym);
 847     }
 848     Sym.makeExternal(createAddressable(false));
 849     ExternalSymbols.insert(&Sym);
 850   }
 851
 852   /// Removes an external symbol. Also removes the underlying Addressable.
 853   void removeExternalSymbol(Symbol &Sym) {
 854     assert(!Sym.isDefined() && !Sym.isAbsolute() &&
 855            "Sym is not an external symbol");
 856     assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set");
 857     ExternalSymbols.erase(&Sym);
 858     Addressable &Base = *Sym.Base;
 859     destroySymbol(Sym);
 860     destroyAddressable(Base);
 861   }
 862
 863   /// Remove an absolute symbol. Also removes the underlying Addressable.
 864   void removeAbsoluteSymbol(Symbol &Sym) {
 865     assert(!Sym.isDefined() && Sym.isAbsolute() &&
 866            "Sym is not an absolute symbol");
 867     assert(AbsoluteSymbols.count(&Sym) &&
 868            "Symbol is not in the absolute symbols set");
 869     AbsoluteSymbols.erase(&Sym);
 870     Addressable &Base = *Sym.Base;
 871     destroySymbol(Sym);
 872     destroyAddressable(Base);
 873   }
 874
 875   /// Removes defined symbols. Does not remove the underlying block.
 876   void removeDefinedSymbol(Symbol &Sym) {
 877     assert(Sym.isDefined() && "Sym is not a defined symbol");
 878     Sym.getBlock().getSection().removeSymbol(Sym);
 879     destroySymbol(Sym);
 880   }
 881
 882   /// Remove a block.
 883   void removeBlock(Block &B) {
 884     Blocks.erase(&B);
 885     destroyBlock(B);
 886   }
 887
 888   /// Dump the graph.
 889   ///
 890   /// If supplied, the EdgeKindToName function will be used to name edge
 891   /// kinds in the debug output. Otherwise raw edge kind numbers will be
 892   /// displayed.
 893   void dump(raw_ostream &OS,
 894             std::function<StringRef(Edge::Kind)> EdegKindToName =
 895                 std::function<StringRef(Edge::Kind)>());
 896
 897 private:
 898   // Put the BumpPtrAllocator first so that we don't free any of the underlying
 899   // memory until the Symbol/Addressable destructors have been run.
 900   BumpPtrAllocator Allocator;
 901
 902   std::string Name;
 903   unsigned PointerSize;
 904   support::endianness Endianness;
 905   BlockSet Blocks;
 906   SectionList Sections;
 907   ExternalSymbolSet ExternalSymbols;
 908   ExternalSymbolSet AbsoluteSymbols;
 909 };
 910
 911 /// A function for mutating LinkGraphs.
 912 using LinkGraphPassFunction = std::function<Error(LinkGraph &)>;
 913
 914 /// A list of LinkGraph passes.
 915 using LinkGraphPassList = std::vector<LinkGraphPassFunction>;
 916
 917 /// An LinkGraph pass configuration, consisting of a list of pre-prune,
 918 /// post-prune, and post-fixup passes.
 919 struct PassConfiguration {
 920
 921   /// Pre-prune passes.
 922   ///
 923   /// These passes are called on the graph after it is built, and before any
 924   /// symbols have been pruned.
 925   ///
 926   /// Notable use cases: Marking symbols live or should-discard.
 927   LinkGraphPassList PrePrunePasses;
 928
 929   /// Post-prune passes.
 930   ///
 931   /// These passes are called on the graph after dead stripping, but before
 932   /// fixups are applied.
 933   ///
 934   /// Notable use cases: Building GOT, stub, and TLV symbols.
 935   LinkGraphPassList PostPrunePasses;
 936
 937   /// Post-fixup passes.
 938   ///
 939   /// These passes are called on the graph after block contents has been copied
 940   /// to working memory, and fixups applied.
 941   ///
 942   /// Notable use cases: Testing and validation.
 943   LinkGraphPassList PostFixupPasses;
 944 };
 945
 946 /// A map of symbol names to resolved addresses.
 947 using AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>;
 948
 949 /// A function object to call with a resolved symbol map (See AsyncLookupResult)
 950 /// or an error if resolution failed.
 951 class JITLinkAsyncLookupContinuation {
 952 public:
 953   virtual ~JITLinkAsyncLookupContinuation() {}
 954   virtual void run(Expected<AsyncLookupResult> LR) = 0;
 955
 956 private:
 957   virtual void anchor();
 958 };
 959
 960 /// Create a lookup continuation from a function object.
 961 template <typename Continuation>
 962 std::unique_ptr<JITLinkAsyncLookupContinuation>
 963 createLookupContinuation(Continuation Cont) {
 964
 965   class Impl final : public JITLinkAsyncLookupContinuation {
 966   public:
 967     Impl(Continuation C) : C(std::move(C)) {}
 968     void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); }
 969
 970   private:
 971     Continuation C;
 972   };
 973
 974   return std::make_unique<Impl>(std::move(Cont));
 975 }
 976
 977 /// Holds context for a single jitLink invocation.
 978 class JITLinkContext {
 979 public:
 980   /// Destroy a JITLinkContext.
 981   virtual ~JITLinkContext();
 982
 983   /// Return the MemoryManager to be used for this link.
 984   virtual JITLinkMemoryManager &getMemoryManager() = 0;
 985
 986   /// Returns a StringRef for the object buffer.
 987   /// This method can not be called once takeObjectBuffer has been called.
 988   virtual MemoryBufferRef getObjectBuffer() const = 0;
 989
 990   /// Notify this context that linking failed.
 991   /// Called by JITLink if linking cannot be completed.
 992   virtual void notifyFailed(Error Err) = 0;
 993
 994   /// Called by JITLink to resolve external symbols. This method is passed a
 995   /// lookup continutation which it must call with a result to continue the
 996   /// linking process.
 997   virtual void lookup(const DenseSet<StringRef> &Symbols,
 998                       std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0;
 999
1000   /// Called by JITLink once all defined symbols in the graph have been assigned
1001   /// their final memory locations in the target process. At this point the
1002   /// LinkGraph can be inspected to build a symbol table, however the block
1003   /// content will not generally have been copied to the target location yet.
1004   virtual void notifyResolved(LinkGraph &G) = 0;
1005
1006   /// Called by JITLink to notify the context that the object has been
1007   /// finalized (i.e. emitted to memory and memory permissions set). If all of
1008   /// this objects dependencies have also been finalized then the code is ready
1009   /// to run.
1010   virtual void
1011   notifyFinalized(std::unique_ptr<JITLinkMemoryManager::Allocation> A) = 0;
1012
1013   /// Called by JITLink prior to linking to determine whether default passes for
1014   /// the target should be added. The default implementation returns true.
1015   /// If subclasses override this method to return false for any target then
1016   /// they are required to fully configure the pass pipeline for that target.
1017   virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;
1018
1019   /// Returns the mark-live pass to be used for this link. If no pass is
1020   /// returned (the default) then the target-specific linker implementation will
1021   /// choose a conservative default (usually marking all symbols live).
1022   /// This function is only called if shouldAddDefaultTargetPasses returns true,
1023   /// otherwise the JITContext is responsible for adding a mark-live pass in
1024   /// modifyPassConfig.
1025   virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const;
1026
1027   /// Called by JITLink to modify the pass pipeline prior to linking.
1028   /// The default version performs no modification.
1029   virtual Error modifyPassConfig(const Triple &TT, PassConfiguration &Config);
1030 };
1031
1032 /// Marks all symbols in a graph live. This can be used as a default,
1033 /// conservative mark-live implementation.
1034 Error markAllSymbolsLive(LinkGraph &G);
1035
1036 /// Basic JITLink implementation.
1037 ///
1038 /// This function will use sensible defaults for GOT and Stub handling.
1039 void jitLink(std::unique_ptr<JITLinkContext> Ctx);
1040
1041 } // end namespace jitlink
1042 } // end namespace llvm
1043
1044 #endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H