contrib/llvm/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 /// Base class for errors originating in JIT linker, e.g. missing relocation
  38 /// support.
  39 class JITLinkError : public ErrorInfo<JITLinkError> {
  40 public:
  41   static char ID;
  42
  43   JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}
  44
  45   void log(raw_ostream &OS) const override;
  46   const std::string &getErrorMessage() const { return ErrMsg; }
  47   std::error_code convertToErrorCode() const override;
  48
  49 private:
  50   std::string ErrMsg;
  51 };
  52
  53 // Forward declare the Atom class.
  54 class Atom;
  55
  56 /// Edge class. Represents both object file relocations, as well as layout and
  57 /// keep-alive constraints.
  58 class Edge {
  59 public:
  60   using Kind = uint8_t;
  61
  62   using GenericEdgeKind = enum : Kind {
  63     Invalid,                    // Invalid edge value.
  64     FirstKeepAlive,             // Keeps target alive. Offset/addend zero.
  65     KeepAlive = FirstKeepAlive, // Tag first edge kind that preserves liveness.
  66     LayoutNext,                 // Layout constraint. Offset/Addend zero.
  67     FirstRelocation             // First architecture specific relocation.
  68   };
  69
  70   using OffsetT = uint32_t;
  71   using AddendT = int64_t;
  72
  73   Edge(Kind K, OffsetT Offset, Atom &Target, AddendT Addend)
  74       : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
  75
  76   OffsetT getOffset() const { return 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   Atom &getTarget() const { return *Target; }
  86   void setTarget(Atom &Target) { this->Target = &Target; }
  87   AddendT getAddend() const { return Addend; }
  88   void setAddend(AddendT Addend) { this->Addend = Addend; }
  89
  90 private:
  91   Atom *Target;
  92   OffsetT Offset;
  93   AddendT Addend;
  94   Kind K = 0;
  95 };
  96
  97 using EdgeVector = std::vector<Edge>;
  98
  99 const StringRef getGenericEdgeKindName(Edge::Kind K);
 100
 101 /// Base Atom class. Used by absolute and undefined atoms.
 102 class Atom {
 103   friend class AtomGraph;
 104
 105 protected:
 106   /// Create a named (as yet unresolved) atom.
 107   Atom(StringRef Name)
 108       : Name(Name), IsDefined(false), IsLive(false), ShouldDiscard(false),
 109         IsGlobal(false), IsAbsolute(false), IsCallable(false),
 110         IsExported(false), IsWeak(false), HasLayoutNext(false),
 111         IsCommon(false) {}
 112
 113   /// Create an absolute symbol atom.
 114   Atom(StringRef Name, JITTargetAddress Address)
 115       : Name(Name), Address(Address), IsDefined(true), IsLive(false),
 116         ShouldDiscard(false), IsGlobal(false), IsAbsolute(false),
 117         IsCallable(false), IsExported(false), IsWeak(false),
 118         HasLayoutNext(false), IsCommon(false) {}
 119
 120 public:
 121   /// Returns true if this atom has a name.
 122   bool hasName() const { return Name != StringRef(); }
 123
 124   /// Returns the name of this atom.
 125   StringRef getName() const { return Name; }
 126
 127   /// Returns the current target address of this atom.
 128   /// The initial target address (for atoms that have one) will be taken from
 129   /// the input object file's virtual address space. During the layout phase
 130   /// of JIT linking the atom's address will be updated to point to its final
 131   /// address in the JIT'd process.
 132   JITTargetAddress getAddress() const { return Address; }
 133
 134   /// Set the current target address of this atom.
 135   void setAddress(JITTargetAddress Address) { this->Address = Address; }
 136
 137   /// Returns true if this is a defined atom.
 138   bool isDefined() const { return IsDefined; }
 139
 140   /// Returns true if this atom is marked as live.
 141   bool isLive() const { return IsLive; }
 142
 143   /// Mark this atom as live.
 144   ///
 145   /// Note: Only defined and absolute atoms can be marked live.
 146   void setLive(bool IsLive) {
 147     assert((IsDefined || IsAbsolute || !IsLive) &&
 148            "Only defined and absolute atoms can be marked live");
 149     this->IsLive = IsLive;
 150   }
 151
 152   /// Returns true if this atom should be discarded during pruning.
 153   bool shouldDiscard() const { return ShouldDiscard; }
 154
 155   /// Mark this atom to be discarded.
 156   ///
 157   /// Note: Only defined and absolute atoms can be marked live.
 158   void setShouldDiscard(bool ShouldDiscard) {
 159     assert((IsDefined || IsAbsolute || !ShouldDiscard) &&
 160            "Only defined and absolute atoms can be marked live");
 161     this->ShouldDiscard = ShouldDiscard;
 162   }
 163
 164   /// Returns true if this definition is global (i.e. visible outside this
 165   /// linkage unit).
 166   ///
 167   /// Note: This is distict from Exported, which means visibile outside the
 168   /// JITDylib that this graph is being linked in to.
 169   bool isGlobal() const { return IsGlobal; }
 170
 171   /// Mark this atom as global.
 172   void setGlobal(bool IsGlobal) { this->IsGlobal = IsGlobal; }
 173
 174   /// Returns true if this atom represents an absolute symbol.
 175   bool isAbsolute() const { return IsAbsolute; }
 176
 177   /// Returns true if this atom is known to be callable.
 178   ///
 179   /// Primarily provided for easy interoperability with ORC, which uses the
 180   /// JITSymbolFlags::Common flag to identify symbols that can be interposed
 181   /// with stubs.
 182   bool isCallable() const { return IsCallable; }
 183
 184   /// Mark this atom as callable.
 185   void setCallable(bool IsCallable) {
 186     assert((IsDefined || IsAbsolute || !IsCallable) &&
 187            "Callable atoms must be defined or absolute");
 188     this->IsCallable = IsCallable;
 189   }
 190
 191   /// Returns true if this atom should appear in the symbol table of a final
 192   /// linked image.
 193   bool isExported() const { return IsExported; }
 194
 195   /// Mark this atom as exported.
 196   void setExported(bool IsExported) {
 197     assert((!IsExported || ((IsDefined || IsAbsolute) && hasName())) &&
 198            "Exported atoms must have names");
 199     this->IsExported = IsExported;
 200   }
 201
 202   /// Returns true if this is a weak symbol.
 203   bool isWeak() const { return IsWeak; }
 204
 205   /// Mark this atom as weak.
 206   void setWeak(bool IsWeak) { this->IsWeak = IsWeak; }
 207
 208 private:
 209   StringRef Name;
 210   JITTargetAddress Address = 0;
 211
 212   bool IsDefined : 1;
 213   bool IsLive : 1;
 214   bool ShouldDiscard : 1;
 215
 216   bool IsGlobal : 1;
 217   bool IsAbsolute : 1;
 218   bool IsCallable : 1;
 219   bool IsExported : 1;
 220   bool IsWeak : 1;
 221
 222 protected:
 223   // These flags only make sense for DefinedAtom, but we can minimize the size
 224   // of DefinedAtom by defining them here.
 225   bool HasLayoutNext : 1;
 226   bool IsCommon : 1;
 227 };
 228
 229 // Forward declare DefinedAtom.
 230 class DefinedAtom;
 231
 232 raw_ostream &operator<<(raw_ostream &OS, const Atom &A);
 233 void printEdge(raw_ostream &OS, const Atom &FixupAtom, const Edge &E,
 234                StringRef EdgeKindName);
 235
 236 /// Represents a section address range via a pair of DefinedAtom pointers to
 237 /// the first and last atoms in the section.
 238 class SectionRange {
 239 public:
 240   SectionRange() = default;
 241   SectionRange(DefinedAtom *First, DefinedAtom *Last)
 242       : First(First), Last(Last) {}
 243   DefinedAtom *getFirstAtom() const {
 244     assert((!Last || First) && "First can not be null if end is non-null");
 245     return First;
 246   }
 247   DefinedAtom *getLastAtom() const {
 248     assert((First || !Last) && "Last can not be null if start is non-null");
 249     return Last;
 250   }
 251   bool isEmpty() const {
 252     assert((First || !Last) && "Last can not be null if start is non-null");
 253     return !First;
 254   }
 255   JITTargetAddress getStart() const;
 256   JITTargetAddress getEnd() const;
 257   uint64_t getSize() const;
 258
 259 private:
 260   DefinedAtom *First = nullptr;
 261   DefinedAtom *Last = nullptr;
 262 };
 263
 264 /// Represents an object file section.
 265 class Section {
 266   friend class AtomGraph;
 267
 268 private:
 269   Section(StringRef Name, uint32_t Alignment, sys::Memory::ProtectionFlags Prot,
 270           unsigned Ordinal, bool IsZeroFill)
 271       : Name(Name), Alignment(Alignment), Prot(Prot), Ordinal(Ordinal),
 272         IsZeroFill(IsZeroFill) {
 273     assert(isPowerOf2_32(Alignment) && "Alignments must be a power of 2");
 274   }
 275
 276   using DefinedAtomSet = DenseSet<DefinedAtom *>;
 277
 278 public:
 279   using atom_iterator = DefinedAtomSet::iterator;
 280   using const_atom_iterator = DefinedAtomSet::const_iterator;
 281
 282   ~Section();
 283   StringRef getName() const { return Name; }
 284   uint32_t getAlignment() const { return Alignment; }
 285   sys::Memory::ProtectionFlags getProtectionFlags() const { return Prot; }
 286   unsigned getSectionOrdinal() const { return Ordinal; }
 287   size_t getNextAtomOrdinal() { return ++NextAtomOrdinal; }
 288
 289   bool isZeroFill() const { return IsZeroFill; }
 290
 291   /// Returns an iterator over the atoms in the section (in no particular
 292   /// order).
 293   iterator_range<atom_iterator> atoms() {
 294     return make_range(DefinedAtoms.begin(), DefinedAtoms.end());
 295   }
 296
 297   /// Returns an iterator over the atoms in the section (in no particular
 298   /// order).
 299   iterator_range<const_atom_iterator> atoms() const {
 300     return make_range(DefinedAtoms.begin(), DefinedAtoms.end());
 301   }
 302
 303   /// Return the number of atoms in this section.
 304   DefinedAtomSet::size_type atoms_size() { return DefinedAtoms.size(); }
 305
 306   /// Return true if this section contains no atoms.
 307   bool atoms_empty() const { return DefinedAtoms.empty(); }
 308
 309   /// Returns the range of this section as the pair of atoms with the lowest
 310   /// and highest target address. This operation is expensive, as it
 311   /// must traverse all atoms in the section.
 312   ///
 313   /// Note: If the section is empty, both values will be null. The section
 314   /// address will evaluate to null, and the size to zero. If the section
 315   /// contains a single atom both values will point to it, the address will
 316   /// evaluate to the address of that atom, and the size will be the size of
 317   /// that atom.
 318   SectionRange getRange() const;
 319
 320 private:
 321   void addAtom(DefinedAtom &DA) {
 322     assert(!DefinedAtoms.count(&DA) && "Atom is already in this section");
 323     DefinedAtoms.insert(&DA);
 324   }
 325
 326   void removeAtom(DefinedAtom &DA) {
 327     assert(DefinedAtoms.count(&DA) && "Atom is not in this section");
 328     DefinedAtoms.erase(&DA);
 329   }
 330
 331   StringRef Name;
 332   uint32_t Alignment = 0;
 333   sys::Memory::ProtectionFlags Prot;
 334   unsigned Ordinal = 0;
 335   unsigned NextAtomOrdinal = 0;
 336   bool IsZeroFill = false;
 337   DefinedAtomSet DefinedAtoms;
 338 };
 339
 340 /// Defined atom class. Suitable for use by defined named and anonymous
 341 /// atoms.
 342 class DefinedAtom : public Atom {
 343   friend class AtomGraph;
 344
 345 private:
 346   DefinedAtom(Section &Parent, JITTargetAddress Address, uint32_t Alignment)
 347       : Atom("", Address), Parent(Parent), Ordinal(Parent.getNextAtomOrdinal()),
 348         Alignment(Alignment) {
 349     assert(isPowerOf2_32(Alignment) && "Alignments must be a power of two");
 350   }
 351
 352   DefinedAtom(Section &Parent, StringRef Name, JITTargetAddress Address,
 353               uint32_t Alignment)
 354       : Atom(Name, Address), Parent(Parent),
 355         Ordinal(Parent.getNextAtomOrdinal()), Alignment(Alignment) {
 356     assert(isPowerOf2_32(Alignment) && "Alignments must be a power of two");
 357   }
 358
 359 public:
 360   using edge_iterator = EdgeVector::iterator;
 361
 362   Section &getSection() const { return Parent; }
 363
 364   uint64_t getSize() const { return Size; }
 365
 366   StringRef getContent() const {
 367     assert(!Parent.isZeroFill() && "Trying to get content for zero-fill atom");
 368     assert(Size <= std::numeric_limits<size_t>::max() &&
 369            "Content size too large");
 370     return {ContentPtr, static_cast<size_t>(Size)};
 371   }
 372   void setContent(StringRef Content) {
 373     assert(!Parent.isZeroFill() && "Calling setContent on zero-fill atom?");
 374     ContentPtr = Content.data();
 375     Size = Content.size();
 376   }
 377
 378   bool isZeroFill() const { return Parent.isZeroFill(); }
 379
 380   void setZeroFill(uint64_t Size) {
 381     assert(Parent.isZeroFill() && !ContentPtr &&
 382            "Can't set zero-fill length of a non zero-fill atom");
 383     this->Size = Size;
 384   }
 385
 386   uint64_t getZeroFillSize() const {
 387     assert(Parent.isZeroFill() &&
 388            "Can't get zero-fill length of a non zero-fill atom");
 389     return Size;
 390   }
 391
 392   uint32_t getAlignment() const { return Alignment; }
 393
 394   bool hasLayoutNext() const { return HasLayoutNext; }
 395   void setLayoutNext(DefinedAtom &Next) {
 396     assert(!HasLayoutNext && "Atom already has layout-next constraint");
 397     HasLayoutNext = true;
 398     Edges.push_back(Edge(Edge::LayoutNext, 0, Next, 0));
 399   }
 400   DefinedAtom &getLayoutNext() {
 401     assert(HasLayoutNext && "Atom does not have a layout-next constraint");
 402     DefinedAtom *Next = nullptr;
 403     for (auto &E : edges())
 404       if (E.getKind() == Edge::LayoutNext) {
 405         assert(E.getTarget().isDefined() &&
 406                "layout-next target atom must be a defined atom");
 407         Next = static_cast<DefinedAtom *>(&E.getTarget());
 408         break;
 409       }
 410     assert(Next && "Missing LayoutNext edge");
 411     return *Next;
 412   }
 413
 414   bool isCommon() const { return IsCommon; }
 415
 416   void addEdge(Edge::Kind K, Edge::OffsetT Offset, Atom &Target,
 417                Edge::AddendT Addend) {
 418     assert(K != Edge::LayoutNext &&
 419            "Layout edges should be added via setLayoutNext");
 420     Edges.push_back(Edge(K, Offset, Target, Addend));
 421   }
 422
 423   iterator_range<edge_iterator> edges() {
 424     return make_range(Edges.begin(), Edges.end());
 425   }
 426   size_t edges_size() const { return Edges.size(); }
 427   bool edges_empty() const { return Edges.empty(); }
 428
 429   unsigned getOrdinal() const { return Ordinal; }
 430
 431 private:
 432   void setCommon(uint64_t Size) {
 433     assert(ContentPtr == 0 && "Atom already has content?");
 434     IsCommon = true;
 435     setZeroFill(Size);
 436   }
 437
 438   EdgeVector Edges;
 439   uint64_t Size = 0;
 440   Section &Parent;
 441   const char *ContentPtr = nullptr;
 442   unsigned Ordinal = 0;
 443   uint32_t Alignment = 0;
 444 };
 445
 446 inline JITTargetAddress SectionRange::getStart() const {
 447   return First ? First->getAddress() : 0;
 448 }
 449
 450 inline JITTargetAddress SectionRange::getEnd() const {
 451   return Last ? Last->getAddress() + Last->getSize() : 0;
 452 }
 453
 454 inline uint64_t SectionRange::getSize() const { return getEnd() - getStart(); }
 455
 456 inline SectionRange Section::getRange() const {
 457   if (atoms_empty())
 458     return SectionRange();
 459   DefinedAtom *First = *DefinedAtoms.begin(), *Last = *DefinedAtoms.begin();
 460   for (auto *DA : atoms()) {
 461     if (DA->getAddress() < First->getAddress())
 462       First = DA;
 463     if (DA->getAddress() > Last->getAddress())
 464       Last = DA;
 465   }
 466   return SectionRange(First, Last);
 467 }
 468
 469 class AtomGraph {
 470 private:
 471   using SectionList = std::vector<std::unique_ptr<Section>>;
 472   using AddressToAtomMap = std::map<JITTargetAddress, DefinedAtom *>;
 473   using NamedAtomMap = DenseMap<StringRef, Atom *>;
 474   using ExternalAtomSet = DenseSet<Atom *>;
 475
 476 public:
 477   using external_atom_iterator = ExternalAtomSet::iterator;
 478
 479   using section_iterator = pointee_iterator<SectionList::iterator>;
 480   using const_section_iterator = pointee_iterator<SectionList::const_iterator>;
 481
 482   template <typename SecItrT, typename AtomItrT, typename T>
 483   class defined_atom_iterator_impl
 484       : public iterator_facade_base<
 485             defined_atom_iterator_impl<SecItrT, AtomItrT, T>,
 486             std::forward_iterator_tag, T> {
 487   public:
 488     defined_atom_iterator_impl() = default;
 489
 490     defined_atom_iterator_impl(SecItrT SI, SecItrT SE)
 491         : SI(SI), SE(SE),
 492           AI(SI != SE ? SI->atoms().begin() : Section::atom_iterator()) {
 493       moveToNextAtomOrEnd();
 494     }
 495
 496     bool operator==(const defined_atom_iterator_impl &RHS) const {
 497       return (SI == RHS.SI) && (AI == RHS.AI);
 498     }
 499
 500     T operator*() const {
 501       assert(AI != SI->atoms().end() && "Dereferencing end?");
 502       return *AI;
 503     }
 504
 505     defined_atom_iterator_impl operator++() {
 506       ++AI;
 507       moveToNextAtomOrEnd();
 508       return *this;
 509     }
 510
 511   private:
 512     void moveToNextAtomOrEnd() {
 513       while (SI != SE && AI == SI->atoms().end()) {
 514         ++SI;
 515         if (SI == SE)
 516           AI = Section::atom_iterator();
 517         else
 518           AI = SI->atoms().begin();
 519       }
 520     }
 521
 522     SecItrT SI, SE;
 523     AtomItrT AI;
 524   };
 525
 526   using defined_atom_iterator =
 527       defined_atom_iterator_impl<section_iterator, Section::atom_iterator,
 528                                  DefinedAtom *>;
 529
 530   using const_defined_atom_iterator =
 531       defined_atom_iterator_impl<const_section_iterator,
 532                                  Section::const_atom_iterator,
 533                                  const DefinedAtom *>;
 534
 535   AtomGraph(std::string Name, unsigned PointerSize,
 536             support::endianness Endianness)
 537       : Name(std::move(Name)), PointerSize(PointerSize),
 538         Endianness(Endianness) {}
 539
 540   /// Returns the name of this graph (usually the name of the original
 541   /// underlying MemoryBuffer).
 542   const std::string &getName() { return Name; }
 543
 544   /// Returns the pointer size for use in this graph.
 545   unsigned getPointerSize() const { return PointerSize; }
 546
 547   /// Returns the endianness of atom-content in this graph.
 548   support::endianness getEndianness() const { return Endianness; }
 549
 550   /// Create a section with the given name, protection flags, and alignment.
 551   Section &createSection(StringRef Name, uint32_t Alignment,
 552                          sys::Memory::ProtectionFlags Prot, bool IsZeroFill) {
 553     std::unique_ptr<Section> Sec(
 554         new Section(Name, Alignment, Prot, Sections.size(), IsZeroFill));
 555     Sections.push_back(std::move(Sec));
 556     return *Sections.back();
 557   }
 558
 559   /// Add an external atom representing an undefined symbol in this graph.
 560   Atom &addExternalAtom(StringRef Name) {
 561     assert(!NamedAtoms.count(Name) && "Duplicate named atom inserted");
 562     Atom *A = reinterpret_cast<Atom *>(
 563         AtomAllocator.Allocate(sizeof(Atom), alignof(Atom)));
 564     new (A) Atom(Name);
 565     ExternalAtoms.insert(A);
 566     NamedAtoms[Name] = A;
 567     return *A;
 568   }
 569
 570   /// Add an external atom representing an absolute symbol.
 571   Atom &addAbsoluteAtom(StringRef Name, JITTargetAddress Addr) {
 572     assert(!NamedAtoms.count(Name) && "Duplicate named atom inserted");
 573     Atom *A = reinterpret_cast<Atom *>(
 574         AtomAllocator.Allocate(sizeof(Atom), alignof(Atom)));
 575     new (A) Atom(Name, Addr);
 576     AbsoluteAtoms.insert(A);
 577     NamedAtoms[Name] = A;
 578     return *A;
 579   }
 580
 581   /// Add an anonymous defined atom to the graph.
 582   ///
 583   /// Anonymous atoms have content but no name. They must have an address.
 584   DefinedAtom &addAnonymousAtom(Section &Parent, JITTargetAddress Address,
 585                                 uint32_t Alignment) {
 586     DefinedAtom *A = reinterpret_cast<DefinedAtom *>(
 587         AtomAllocator.Allocate(sizeof(DefinedAtom), alignof(DefinedAtom)));
 588     new (A) DefinedAtom(Parent, Address, Alignment);
 589     Parent.addAtom(*A);
 590     getAddrToAtomMap()[A->getAddress()] = A;
 591     return *A;
 592   }
 593
 594   /// Add a defined atom to the graph.
 595   ///
 596   /// Allocates and constructs a DefinedAtom instance with the given parent,
 597   /// name, address, and alignment.
 598   DefinedAtom &addDefinedAtom(Section &Parent, StringRef Name,
 599                               JITTargetAddress Address, uint32_t Alignment) {
 600     assert(!NamedAtoms.count(Name) && "Duplicate named atom inserted");
 601     DefinedAtom *A = reinterpret_cast<DefinedAtom *>(
 602         AtomAllocator.Allocate(sizeof(DefinedAtom), alignof(DefinedAtom)));
 603     new (A) DefinedAtom(Parent, Name, Address, Alignment);
 604     Parent.addAtom(*A);
 605     getAddrToAtomMap()[A->getAddress()] = A;
 606     NamedAtoms[Name] = A;
 607     return *A;
 608   }
 609
 610   /// Add a common symbol atom to the graph.
 611   ///
 612   /// Adds a common-symbol atom to the graph with the given parent, name,
 613   /// address, alignment and size.
 614   DefinedAtom &addCommonAtom(Section &Parent, StringRef Name,
 615                              JITTargetAddress Address, uint32_t Alignment,
 616                              uint64_t Size) {
 617     assert(!NamedAtoms.count(Name) && "Duplicate named atom inserted");
 618     DefinedAtom *A = reinterpret_cast<DefinedAtom *>(
 619         AtomAllocator.Allocate(sizeof(DefinedAtom), alignof(DefinedAtom)));
 620     new (A) DefinedAtom(Parent, Name, Address, Alignment);
 621     A->setCommon(Size);
 622     Parent.addAtom(*A);
 623     NamedAtoms[Name] = A;
 624     return *A;
 625   }
 626
 627   iterator_range<section_iterator> sections() {
 628     return make_range(section_iterator(Sections.begin()),
 629                       section_iterator(Sections.end()));
 630   }
 631
 632   /// Returns the section with the given name if it exists, otherwise returns
 633   /// null.
 634   Section *findSectionByName(StringRef Name) {
 635     for (auto &S : sections())
 636       if (S.getName() == Name)
 637         return &S;
 638     return nullptr;
 639   }
 640
 641   iterator_range<external_atom_iterator> external_atoms() {
 642     return make_range(ExternalAtoms.begin(), ExternalAtoms.end());
 643   }
 644
 645   iterator_range<external_atom_iterator> absolute_atoms() {
 646     return make_range(AbsoluteAtoms.begin(), AbsoluteAtoms.end());
 647   }
 648
 649   iterator_range<defined_atom_iterator> defined_atoms() {
 650     return make_range(defined_atom_iterator(Sections.begin(), Sections.end()),
 651                       defined_atom_iterator(Sections.end(), Sections.end()));
 652   }
 653
 654   iterator_range<const_defined_atom_iterator> defined_atoms() const {
 655     return make_range(
 656         const_defined_atom_iterator(Sections.begin(), Sections.end()),
 657         const_defined_atom_iterator(Sections.end(), Sections.end()));
 658   }
 659
 660   /// Returns the atom with the given name, which must exist in this graph.
 661   Atom &getAtomByName(StringRef Name) {
 662     auto I = NamedAtoms.find(Name);
 663     assert(I != NamedAtoms.end() && "Name not in NamedAtoms map");
 664     return *I->second;
 665   }
 666
 667   /// Returns the atom with the given name, which must exist in this graph and
 668   /// be a DefinedAtom.
 669   DefinedAtom &getDefinedAtomByName(StringRef Name) {
 670     auto &A = getAtomByName(Name);
 671     assert(A.isDefined() && "Atom is not a defined atom");
 672     return static_cast<DefinedAtom &>(A);
 673   }
 674
 675   /// Search for the given atom by name.
 676   /// Returns the atom (if found) or an error (if no atom with this name
 677   /// exists).
 678   Expected<Atom &> findAtomByName(StringRef Name) {
 679     auto I = NamedAtoms.find(Name);
 680     if (I == NamedAtoms.end())
 681       return make_error<JITLinkError>("No atom named " + Name);
 682     return *I->second;
 683   }
 684
 685   /// Search for the given defined atom by name.
 686   /// Returns the defined atom (if found) or an error (if no atom with this
 687   /// name exists, or if one exists but is not a defined atom).
 688   Expected<DefinedAtom &> findDefinedAtomByName(StringRef Name) {
 689     auto I = NamedAtoms.find(Name);
 690     if (I == NamedAtoms.end())
 691       return make_error<JITLinkError>("No atom named " + Name);
 692     if (!I->second->isDefined())
 693       return make_error<JITLinkError>("Atom " + Name +
 694                                       " exists but is not a "
 695                                       "defined atom");
 696     return static_cast<DefinedAtom &>(*I->second);
 697   }
 698
 699   /// Returns the atom covering the given address, or an error if no such atom
 700   /// exists.
 701   ///
 702   /// Returns null if no atom exists at the given address.
 703   DefinedAtom *getAtomByAddress(JITTargetAddress Address) {
 704     refreshAddrToAtomCache();
 705
 706     // If there are no defined atoms, bail out early.
 707     if (AddrToAtomCache->empty())
 708       return nullptr;
 709
 710     // Find the atom *after* the given address.
 711     auto I = AddrToAtomCache->upper_bound(Address);
 712
 713     // If this address falls before any known atom, bail out.
 714     if (I == AddrToAtomCache->begin())
 715       return nullptr;
 716
 717     // The atom we're looking for is the one before the atom we found.
 718     --I;
 719
 720     // Otherwise range check the atom that was found.
 721     assert(!I->second->getContent().empty() && "Atom content not set");
 722     if (Address >= I->second->getAddress() + I->second->getContent().size())
 723       return nullptr;
 724
 725     return I->second;
 726   }
 727
 728   /// Like getAtomByAddress, but returns an Error if the given address is not
 729   /// covered by an atom, rather than a null pointer.
 730   Expected<DefinedAtom &> findAtomByAddress(JITTargetAddress Address) {
 731     if (auto *DA = getAtomByAddress(Address))
 732       return *DA;
 733     return make_error<JITLinkError>("No atom at address " +
 734                                     formatv("{0:x16}", Address));
 735   }
 736
 737   // Remove the given external atom from the graph.
 738   void removeExternalAtom(Atom &A) {
 739     assert(!A.isDefined() && !A.isAbsolute() && "A is not an external atom");
 740     assert(ExternalAtoms.count(&A) && "A is not in the external atoms set");
 741     ExternalAtoms.erase(&A);
 742     A.~Atom();
 743   }
 744
 745   /// Remove the given absolute atom from the graph.
 746   void removeAbsoluteAtom(Atom &A) {
 747     assert(A.isAbsolute() && "A is not an absolute atom");
 748     assert(AbsoluteAtoms.count(&A) && "A is not in the absolute atoms set");
 749     AbsoluteAtoms.erase(&A);
 750     A.~Atom();
 751   }
 752
 753   /// Remove the given defined atom from the graph.
 754   void removeDefinedAtom(DefinedAtom &DA) {
 755     if (AddrToAtomCache) {
 756       assert(AddrToAtomCache->count(DA.getAddress()) &&
 757              "Cache exists, but does not contain atom");
 758       AddrToAtomCache->erase(DA.getAddress());
 759     }
 760     if (DA.hasName()) {
 761       assert(NamedAtoms.count(DA.getName()) && "Named atom not in map");
 762       NamedAtoms.erase(DA.getName());
 763     }
 764     DA.getSection().removeAtom(DA);
 765     DA.~DefinedAtom();
 766   }
 767
 768   /// Invalidate the atom-to-address map.
 769   void invalidateAddrToAtomMap() { AddrToAtomCache = None; }
 770
 771   /// Dump the graph.
 772   ///
 773   /// If supplied, the EdgeKindToName function will be used to name edge
 774   /// kinds in the debug output. Otherwise raw edge kind numbers will be
 775   /// displayed.
 776   void dump(raw_ostream &OS,
 777             std::function<StringRef(Edge::Kind)> EdegKindToName =
 778                 std::function<StringRef(Edge::Kind)>());
 779
 780 private:
 781   AddressToAtomMap &getAddrToAtomMap() {
 782     refreshAddrToAtomCache();
 783     return *AddrToAtomCache;
 784   }
 785
 786   const AddressToAtomMap &getAddrToAtomMap() const {
 787     refreshAddrToAtomCache();
 788     return *AddrToAtomCache;
 789   }
 790
 791   void refreshAddrToAtomCache() const {
 792     if (!AddrToAtomCache) {
 793       AddrToAtomCache = AddressToAtomMap();
 794       for (auto *DA : defined_atoms())
 795         (*AddrToAtomCache)[DA->getAddress()] = const_cast<DefinedAtom *>(DA);
 796     }
 797   }
 798
 799   // Put the BumpPtrAllocator first so that we don't free any of the atoms in
 800   // it until all of their destructors have been run.
 801   BumpPtrAllocator AtomAllocator;
 802
 803   std::string Name;
 804   unsigned PointerSize;
 805   support::endianness Endianness;
 806   SectionList Sections;
 807   NamedAtomMap NamedAtoms;
 808   ExternalAtomSet ExternalAtoms;
 809   ExternalAtomSet AbsoluteAtoms;
 810   mutable Optional<AddressToAtomMap> AddrToAtomCache;
 811 };
 812
 813 /// A function for mutating AtomGraphs.
 814 using AtomGraphPassFunction = std::function<Error(AtomGraph &)>;
 815
 816 /// A list of atom graph passes.
 817 using AtomGraphPassList = std::vector<AtomGraphPassFunction>;
 818
 819 /// An atom graph pass configuration, consisting of a list of pre-prune,
 820 /// post-prune, and post-fixup passes.
 821 struct PassConfiguration {
 822
 823   /// Pre-prune passes.
 824   ///
 825   /// These passes are called on the graph after it is built, and before any
 826   /// atoms have been pruned.
 827   ///
 828   /// Notable use cases: Marking atoms live or should-discard.
 829   AtomGraphPassList PrePrunePasses;
 830
 831   /// Post-prune passes.
 832   ///
 833   /// These passes are called on the graph after dead and should-discard atoms
 834   /// have been removed, but before fixups are applied.
 835   ///
 836   /// Notable use cases: Building GOT, stub, and TLV atoms.
 837   AtomGraphPassList PostPrunePasses;
 838
 839   /// Post-fixup passes.
 840   ///
 841   /// These passes are called on the graph after atom contents has been copied
 842   /// to working memory, and fixups applied.
 843   ///
 844   /// Notable use cases: Testing and validation.
 845   AtomGraphPassList PostFixupPasses;
 846 };
 847
 848 /// A map of symbol names to resolved addresses.
 849 using AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>;
 850
 851 /// A function to call with a resolved symbol map (See AsyncLookupResult) or an
 852 /// error if resolution failed.
 853 using JITLinkAsyncLookupContinuation =
 854     std::function<void(Expected<AsyncLookupResult> LR)>;
 855
 856 /// An asynchronous symbol lookup. Performs a search (possibly asynchronously)
 857 /// for the given symbols, calling the given continuation with either the result
 858 /// (if the lookup succeeds), or an error (if the lookup fails).
 859 using JITLinkAsyncLookupFunction =
 860     std::function<void(const DenseSet<StringRef> &Symbols,
 861                        JITLinkAsyncLookupContinuation LookupContinuation)>;
 862
 863 /// Holds context for a single jitLink invocation.
 864 class JITLinkContext {
 865 public:
 866   /// Destroy a JITLinkContext.
 867   virtual ~JITLinkContext();
 868
 869   /// Return the MemoryManager to be used for this link.
 870   virtual JITLinkMemoryManager &getMemoryManager() = 0;
 871
 872   /// Returns a StringRef for the object buffer.
 873   /// This method can not be called once takeObjectBuffer has been called.
 874   virtual MemoryBufferRef getObjectBuffer() const = 0;
 875
 876   /// Notify this context that linking failed.
 877   /// Called by JITLink if linking cannot be completed.
 878   virtual void notifyFailed(Error Err) = 0;
 879
 880   /// Called by JITLink to resolve external symbols. This method is passed a
 881   /// lookup continutation which it must call with a result to continue the
 882   /// linking process.
 883   virtual void lookup(const DenseSet<StringRef> &Symbols,
 884                       JITLinkAsyncLookupContinuation LookupContinuation) = 0;
 885
 886   /// Called by JITLink once all defined atoms in the graph have been assigned
 887   /// their final memory locations in the target process. At this point he
 888   /// atom graph can be, inspected to build a symbol table however the atom
 889   /// content will not generally have been copied to the target location yet.
 890   virtual void notifyResolved(AtomGraph &G) = 0;
 891
 892   /// Called by JITLink to notify the context that the object has been
 893   /// finalized (i.e. emitted to memory and memory permissions set). If all of
 894   /// this objects dependencies have also been finalized then the code is ready
 895   /// to run.
 896   virtual void
 897   notifyFinalized(std::unique_ptr<JITLinkMemoryManager::Allocation> A) = 0;
 898
 899   /// Called by JITLink prior to linking to determine whether default passes for
 900   /// the target should be added. The default implementation returns true.
 901   /// If subclasses override this method to return false for any target then
 902   /// they are required to fully configure the pass pipeline for that target.
 903   virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;
 904
 905   /// Returns the mark-live pass to be used for this link. If no pass is
 906   /// returned (the default) then the target-specific linker implementation will
 907   /// choose a conservative default (usually marking all atoms live).
 908   /// This function is only called if shouldAddDefaultTargetPasses returns true,
 909   /// otherwise the JITContext is responsible for adding a mark-live pass in
 910   /// modifyPassConfig.
 911   virtual AtomGraphPassFunction getMarkLivePass(const Triple &TT) const;
 912
 913   /// Called by JITLink to modify the pass pipeline prior to linking.
 914   /// The default version performs no modification.
 915   virtual Error modifyPassConfig(const Triple &TT, PassConfiguration &Config);
 916 };
 917
 918 /// Marks all atoms in a graph live. This can be used as a default, conservative
 919 /// mark-live implementation.
 920 Error markAllAtomsLive(AtomGraph &G);
 921
 922 /// Basic JITLink implementation.
 923 ///
 924 /// This function will use sensible defaults for GOT and Stub handling.
 925 void jitLink(std::unique_ptr<JITLinkContext> Ctx);
 926
 927 } // end namespace jitlink
 928 } // end namespace llvm
 929
 930 #endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H