1351278Sdim//===------------ JITLink.h - JIT linker functionality ----------*- C++ -*-===// 2351278Sdim// 3351278Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351278Sdim// See https://llvm.org/LICENSE.txt for license information. 5351278Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351278Sdim// 7351278Sdim//===----------------------------------------------------------------------===// 8351278Sdim// 9351278Sdim// Contains generic JIT-linker types. 10351278Sdim// 11351278Sdim//===----------------------------------------------------------------------===// 12351278Sdim 13351278Sdim#ifndef LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H 14351278Sdim#define LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H 15351278Sdim 16351278Sdim#include "JITLinkMemoryManager.h" 17351278Sdim#include "llvm/ADT/DenseMap.h" 18351278Sdim#include "llvm/ADT/DenseSet.h" 19351278Sdim#include "llvm/ADT/Optional.h" 20351278Sdim#include "llvm/ADT/Triple.h" 21351278Sdim#include "llvm/ExecutionEngine/JITSymbol.h" 22351278Sdim#include "llvm/Support/Allocator.h" 23351278Sdim#include "llvm/Support/Endian.h" 24351278Sdim#include "llvm/Support/Error.h" 25351278Sdim#include "llvm/Support/FormatVariadic.h" 26351278Sdim#include "llvm/Support/MathExtras.h" 27351278Sdim#include "llvm/Support/Memory.h" 28351278Sdim#include "llvm/Support/MemoryBuffer.h" 29351278Sdim 30351278Sdim#include <map> 31351278Sdim#include <string> 32351278Sdim#include <system_error> 33351278Sdim 34351278Sdimnamespace llvm { 35351278Sdimnamespace jitlink { 36351278Sdim 37360784Sdimclass Symbol; 38360784Sdimclass Section; 39360784Sdim 40351278Sdim/// Base class for errors originating in JIT linker, e.g. missing relocation 41351278Sdim/// support. 42351278Sdimclass JITLinkError : public ErrorInfo<JITLinkError> { 43351278Sdimpublic: 44351278Sdim static char ID; 45351278Sdim 46351278Sdim JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {} 47351278Sdim 48351278Sdim void log(raw_ostream &OS) const override; 49351278Sdim const std::string &getErrorMessage() const { return ErrMsg; } 50351278Sdim std::error_code convertToErrorCode() const override; 51351278Sdim 52351278Sdimprivate: 53351278Sdim std::string ErrMsg; 54351278Sdim}; 55351278Sdim 56360784Sdim/// Represents fixups and constraints in the LinkGraph. 57351278Sdimclass Edge { 58351278Sdimpublic: 59351278Sdim using Kind = uint8_t; 60351278Sdim 61360784Sdim enum GenericEdgeKind : Kind { 62351278Sdim Invalid, // Invalid edge value. 63351278Sdim FirstKeepAlive, // Keeps target alive. Offset/addend zero. 64351278Sdim KeepAlive = FirstKeepAlive, // Tag first edge kind that preserves liveness. 65351278Sdim FirstRelocation // First architecture specific relocation. 66351278Sdim }; 67351278Sdim 68351278Sdim using OffsetT = uint32_t; 69351278Sdim using AddendT = int64_t; 70351278Sdim 71360784Sdim Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend) 72351278Sdim : Target(&Target), Offset(Offset), Addend(Addend), K(K) {} 73351278Sdim 74351278Sdim OffsetT getOffset() const { return Offset; } 75360784Sdim void setOffset(OffsetT Offset) { this->Offset = Offset; } 76351278Sdim Kind getKind() const { return K; } 77351278Sdim void setKind(Kind K) { this->K = K; } 78351278Sdim bool isRelocation() const { return K >= FirstRelocation; } 79351278Sdim Kind getRelocation() const { 80351278Sdim assert(isRelocation() && "Not a relocation edge"); 81351278Sdim return K - FirstRelocation; 82351278Sdim } 83351278Sdim bool isKeepAlive() const { return K >= FirstKeepAlive; } 84360784Sdim Symbol &getTarget() const { return *Target; } 85360784Sdim void setTarget(Symbol &Target) { this->Target = &Target; } 86351278Sdim AddendT getAddend() const { return Addend; } 87351278Sdim void setAddend(AddendT Addend) { this->Addend = Addend; } 88351278Sdim 89351278Sdimprivate: 90360784Sdim Symbol *Target = nullptr; 91360784Sdim OffsetT Offset = 0; 92360784Sdim AddendT Addend = 0; 93351278Sdim Kind K = 0; 94351278Sdim}; 95351278Sdim 96360784Sdim/// Returns the string name of the given generic edge kind, or "unknown" 97360784Sdim/// otherwise. Useful for debugging. 98360784Sdimconst char *getGenericEdgeKindName(Edge::Kind K); 99351278Sdim 100360784Sdim/// Base class for Addressable entities (externals, absolutes, blocks). 101360784Sdimclass Addressable { 102360784Sdim friend class LinkGraph; 103351278Sdim 104351278Sdimprotected: 105360784Sdim Addressable(JITTargetAddress Address, bool IsDefined) 106360784Sdim : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {} 107351278Sdim 108360784Sdim Addressable(JITTargetAddress Address) 109360784Sdim : Address(Address), IsDefined(false), IsAbsolute(true) { 110360784Sdim assert(!(IsDefined && IsAbsolute) && 111360784Sdim "Block cannot be both defined and absolute"); 112360784Sdim } 113351278Sdim 114351278Sdimpublic: 115360784Sdim Addressable(const Addressable &) = delete; 116360784Sdim Addressable &operator=(const Addressable &) = default; 117360784Sdim Addressable(Addressable &&) = delete; 118360784Sdim Addressable &operator=(Addressable &&) = default; 119351278Sdim 120351278Sdim JITTargetAddress getAddress() const { return Address; } 121351278Sdim void setAddress(JITTargetAddress Address) { this->Address = Address; } 122351278Sdim 123360784Sdim /// Returns true if this is a defined addressable, in which case you 124360784Sdim /// can downcast this to a . 125360784Sdim bool isDefined() const { return static_cast<bool>(IsDefined); } 126360784Sdim bool isAbsolute() const { return static_cast<bool>(IsAbsolute); } 127351278Sdim 128360784Sdimprivate: 129360784Sdim JITTargetAddress Address = 0; 130360784Sdim uint64_t IsDefined : 1; 131360784Sdim uint64_t IsAbsolute : 1; 132360784Sdim}; 133351278Sdim 134360784Sdimusing SectionOrdinal = unsigned; 135360784Sdim 136360784Sdim/// An Addressable with content and edges. 137360784Sdimclass Block : public Addressable { 138360784Sdim friend class LinkGraph; 139360784Sdim 140360784Sdimprivate: 141360784Sdim /// Create a zero-fill defined addressable. 142360784Sdim Block(Section &Parent, JITTargetAddress Size, JITTargetAddress Address, 143360784Sdim uint64_t Alignment, uint64_t AlignmentOffset) 144360784Sdim : Addressable(Address, true), Parent(Parent), Size(Size) { 145360784Sdim assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2"); 146360784Sdim assert(AlignmentOffset < Alignment && 147360784Sdim "Alignment offset cannot exceed alignment"); 148360784Sdim assert(AlignmentOffset <= MaxAlignmentOffset && 149360784Sdim "Alignment offset exceeds maximum"); 150360784Sdim P2Align = Alignment ? countTrailingZeros(Alignment) : 0; 151360784Sdim this->AlignmentOffset = AlignmentOffset; 152351278Sdim } 153351278Sdim 154360784Sdim /// Create a defined addressable for the given content. 155360784Sdim Block(Section &Parent, StringRef Content, JITTargetAddress Address, 156360784Sdim uint64_t Alignment, uint64_t AlignmentOffset) 157360784Sdim : Addressable(Address, true), Parent(Parent), Data(Content.data()), 158360784Sdim Size(Content.size()) { 159360784Sdim assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2"); 160360784Sdim assert(AlignmentOffset < Alignment && 161360784Sdim "Alignment offset cannot exceed alignment"); 162360784Sdim assert(AlignmentOffset <= MaxAlignmentOffset && 163360784Sdim "Alignment offset exceeds maximum"); 164360784Sdim P2Align = Alignment ? countTrailingZeros(Alignment) : 0; 165360784Sdim this->AlignmentOffset = AlignmentOffset; 166360784Sdim } 167351278Sdim 168360784Sdimpublic: 169360784Sdim using EdgeVector = std::vector<Edge>; 170360784Sdim using edge_iterator = EdgeVector::iterator; 171360784Sdim using const_edge_iterator = EdgeVector::const_iterator; 172360784Sdim 173360784Sdim Block(const Block &) = delete; 174360784Sdim Block &operator=(const Block &) = delete; 175360784Sdim Block(Block &&) = delete; 176360784Sdim Block &operator=(Block &&) = delete; 177360784Sdim 178360784Sdim /// Return the parent section for this block. 179360784Sdim Section &getSection() const { return Parent; } 180360784Sdim 181360784Sdim /// Returns true if this is a zero-fill block. 182351278Sdim /// 183360784Sdim /// If true, getSize is callable but getContent is not (the content is 184360784Sdim /// defined to be a sequence of zero bytes of length Size). 185360784Sdim bool isZeroFill() const { return !Data; } 186360784Sdim 187360784Sdim /// Returns the size of this defined addressable. 188360784Sdim size_t getSize() const { return Size; } 189360784Sdim 190360784Sdim /// Get the content for this block. Block must not be a zero-fill block. 191360784Sdim StringRef getContent() const { 192360784Sdim assert(Data && "Section does not contain content"); 193360784Sdim return StringRef(Data, Size); 194351278Sdim } 195351278Sdim 196360784Sdim /// Set the content for this block. 197360784Sdim /// Caller is responsible for ensuring the underlying bytes are not 198360784Sdim /// deallocated while pointed to by this block. 199360784Sdim void setContent(StringRef Content) { 200360784Sdim Data = Content.data(); 201360784Sdim Size = Content.size(); 202360784Sdim } 203351278Sdim 204360784Sdim /// Get the alignment for this content. 205360784Sdim uint64_t getAlignment() const { return 1ull << P2Align; } 206351278Sdim 207360784Sdim /// Set the alignment for this content. 208360784Sdim void setAlignment(uint64_t Alignment) { 209360784Sdim assert(isPowerOf2_64(Alignment) && "Alignment must be a power of two"); 210360784Sdim P2Align = Alignment ? countTrailingZeros(Alignment) : 0; 211360784Sdim } 212351278Sdim 213360784Sdim /// Get the alignment offset for this content. 214360784Sdim uint64_t getAlignmentOffset() const { return AlignmentOffset; } 215351278Sdim 216360784Sdim /// Set the alignment offset for this content. 217360784Sdim void setAlignmentOffset(uint64_t AlignmentOffset) { 218360784Sdim assert(AlignmentOffset < (1ull << P2Align) && 219360784Sdim "Alignment offset can't exceed alignment"); 220360784Sdim this->AlignmentOffset = AlignmentOffset; 221351278Sdim } 222351278Sdim 223360784Sdim /// Add an edge to this block. 224360784Sdim void addEdge(Edge::Kind K, Edge::OffsetT Offset, Symbol &Target, 225360784Sdim Edge::AddendT Addend) { 226360784Sdim Edges.push_back(Edge(K, Offset, Target, Addend)); 227360784Sdim } 228351278Sdim 229360784Sdim /// Add an edge by copying an existing one. This is typically used when 230360784Sdim /// moving edges between blocks. 231360784Sdim void addEdge(const Edge &E) { Edges.push_back(E); } 232360784Sdim 233360784Sdim /// Return the list of edges attached to this content. 234360784Sdim iterator_range<edge_iterator> edges() { 235360784Sdim return make_range(Edges.begin(), Edges.end()); 236351278Sdim } 237351278Sdim 238360784Sdim /// Returns the list of edges attached to this content. 239360784Sdim iterator_range<const_edge_iterator> edges() const { 240360784Sdim return make_range(Edges.begin(), Edges.end()); 241360784Sdim } 242351278Sdim 243360784Sdim /// Return the size of the edges list. 244360784Sdim size_t edges_size() const { return Edges.size(); } 245351278Sdim 246360784Sdim /// Returns true if the list of edges is empty. 247360784Sdim bool edges_empty() const { return Edges.empty(); } 248351278Sdim 249360784Sdim /// Remove the edge pointed to by the given iterator. 250360784Sdim /// Invalidates all iterators that point to or past the given one. 251360784Sdim void removeEdge(const_edge_iterator I) { Edges.erase(I); } 252351278Sdim 253360784Sdimprivate: 254360784Sdim static constexpr uint64_t MaxAlignmentOffset = (1ULL << 57) - 1; 255351278Sdim 256360784Sdim uint64_t P2Align : 5; 257360784Sdim uint64_t AlignmentOffset : 57; 258360784Sdim Section &Parent; 259360784Sdim const char *Data = nullptr; 260360784Sdim size_t Size = 0; 261360784Sdim std::vector<Edge> Edges; 262351278Sdim}; 263351278Sdim 264360784Sdim/// Describes symbol linkage. This can be used to make resolve definition 265360784Sdim/// clashes. 266360784Sdimenum class Linkage : uint8_t { 267360784Sdim Strong, 268360784Sdim Weak, 269360784Sdim}; 270351278Sdim 271360784Sdim/// For errors and debugging output. 272360784Sdimconst char *getLinkageName(Linkage L); 273351278Sdim 274360784Sdim/// Defines the scope in which this symbol should be visible: 275360784Sdim/// Default -- Visible in the public interface of the linkage unit. 276360784Sdim/// Hidden -- Visible within the linkage unit, but not exported from it. 277360784Sdim/// Local -- Visible only within the LinkGraph. 278360784Sdimenum class Scope : uint8_t { Default, Hidden, Local }; 279360784Sdim 280360784Sdim/// For debugging output. 281360784Sdimconst char *getScopeName(Scope S); 282360784Sdim 283360784Sdimraw_ostream &operator<<(raw_ostream &OS, const Block &B); 284360784Sdim 285360784Sdim/// Symbol representation. 286360784Sdim/// 287360784Sdim/// Symbols represent locations within Addressable objects. 288360784Sdim/// They can be either Named or Anonymous. 289360784Sdim/// Anonymous symbols have neither linkage nor visibility, and must point at 290360784Sdim/// ContentBlocks. 291360784Sdim/// Named symbols may be in one of four states: 292360784Sdim/// - Null: Default initialized. Assignable, but otherwise unusable. 293360784Sdim/// - Defined: Has both linkage and visibility and points to a ContentBlock 294360784Sdim/// - Common: Has both linkage and visibility, points to a null Addressable. 295360784Sdim/// - External: Has neither linkage nor visibility, points to an external 296360784Sdim/// Addressable. 297360784Sdim/// 298360784Sdimclass Symbol { 299360784Sdim friend class LinkGraph; 300360784Sdim 301360784Sdimprivate: 302360784Sdim Symbol(Addressable &Base, JITTargetAddress Offset, StringRef Name, 303360784Sdim JITTargetAddress Size, Linkage L, Scope S, bool IsLive, 304360784Sdim bool IsCallable) 305360784Sdim : Name(Name), Base(&Base), Offset(Offset), Size(Size) { 306360784Sdim assert(Offset <= MaxOffset && "Offset out of range"); 307360784Sdim setLinkage(L); 308360784Sdim setScope(S); 309360784Sdim setLive(IsLive); 310360784Sdim setCallable(IsCallable); 311360784Sdim } 312360784Sdim 313360784Sdim static Symbol &constructCommon(void *SymStorage, Block &Base, StringRef Name, 314360784Sdim JITTargetAddress Size, Scope S, bool IsLive) { 315360784Sdim assert(SymStorage && "Storage cannot be null"); 316360784Sdim assert(!Name.empty() && "Common symbol name cannot be empty"); 317360784Sdim assert(Base.isDefined() && 318360784Sdim "Cannot create common symbol from undefined block"); 319360784Sdim assert(static_cast<Block &>(Base).getSize() == Size && 320360784Sdim "Common symbol size should match underlying block size"); 321360784Sdim auto *Sym = reinterpret_cast<Symbol *>(SymStorage); 322360784Sdim new (Sym) Symbol(Base, 0, Name, Size, Linkage::Weak, S, IsLive, false); 323360784Sdim return *Sym; 324360784Sdim } 325360784Sdim 326360784Sdim static Symbol &constructExternal(void *SymStorage, Addressable &Base, 327360784Sdim StringRef Name, JITTargetAddress Size, 328360784Sdim Linkage L) { 329360784Sdim assert(SymStorage && "Storage cannot be null"); 330360784Sdim assert(!Base.isDefined() && 331360784Sdim "Cannot create external symbol from defined block"); 332360784Sdim assert(!Name.empty() && "External symbol name cannot be empty"); 333360784Sdim auto *Sym = reinterpret_cast<Symbol *>(SymStorage); 334360784Sdim new (Sym) Symbol(Base, 0, Name, Size, L, Scope::Default, false, false); 335360784Sdim return *Sym; 336360784Sdim } 337360784Sdim 338360784Sdim static Symbol &constructAbsolute(void *SymStorage, Addressable &Base, 339360784Sdim StringRef Name, JITTargetAddress Size, 340360784Sdim Linkage L, Scope S, bool IsLive) { 341360784Sdim assert(SymStorage && "Storage cannot be null"); 342360784Sdim assert(!Base.isDefined() && 343360784Sdim "Cannot create absolute symbol from a defined block"); 344360784Sdim auto *Sym = reinterpret_cast<Symbol *>(SymStorage); 345360784Sdim new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false); 346360784Sdim return *Sym; 347360784Sdim } 348360784Sdim 349360784Sdim static Symbol &constructAnonDef(void *SymStorage, Block &Base, 350360784Sdim JITTargetAddress Offset, 351360784Sdim JITTargetAddress Size, bool IsCallable, 352360784Sdim bool IsLive) { 353360784Sdim assert(SymStorage && "Storage cannot be null"); 354360784Sdim assert(Offset < Base.getSize() && "Symbol offset is outside block"); 355360784Sdim auto *Sym = reinterpret_cast<Symbol *>(SymStorage); 356360784Sdim new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong, 357360784Sdim Scope::Local, IsLive, IsCallable); 358360784Sdim return *Sym; 359360784Sdim } 360360784Sdim 361360784Sdim static Symbol &constructNamedDef(void *SymStorage, Block &Base, 362360784Sdim JITTargetAddress Offset, StringRef Name, 363360784Sdim JITTargetAddress Size, Linkage L, Scope S, 364360784Sdim bool IsLive, bool IsCallable) { 365360784Sdim assert(SymStorage && "Storage cannot be null"); 366360784Sdim assert(Offset < Base.getSize() && "Symbol offset is outside block"); 367360784Sdim assert(!Name.empty() && "Name cannot be empty"); 368360784Sdim auto *Sym = reinterpret_cast<Symbol *>(SymStorage); 369360784Sdim new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable); 370360784Sdim return *Sym; 371360784Sdim } 372360784Sdim 373351278Sdimpublic: 374360784Sdim /// Create a null Symbol. This allows Symbols to be default initialized for 375360784Sdim /// use in containers (e.g. as map values). Null symbols are only useful for 376360784Sdim /// assigning to. 377360784Sdim Symbol() = default; 378360784Sdim 379360784Sdim // Symbols are not movable or copyable. 380360784Sdim Symbol(const Symbol &) = delete; 381360784Sdim Symbol &operator=(const Symbol &) = delete; 382360784Sdim Symbol(Symbol &&) = delete; 383360784Sdim Symbol &operator=(Symbol &&) = delete; 384360784Sdim 385360784Sdim /// Returns true if this symbol has a name. 386360784Sdim bool hasName() const { return !Name.empty(); } 387360784Sdim 388360784Sdim /// Returns the name of this symbol (empty if the symbol is anonymous). 389360784Sdim StringRef getName() const { 390360784Sdim assert((!Name.empty() || getScope() == Scope::Local) && 391360784Sdim "Anonymous symbol has non-local scope"); 392360784Sdim return Name; 393351278Sdim } 394360784Sdim 395360784Sdim /// Returns true if this Symbol has content (potentially) defined within this 396360784Sdim /// object file (i.e. is anything but an external or absolute symbol). 397360784Sdim bool isDefined() const { 398360784Sdim assert(Base && "Attempt to access null symbol"); 399360784Sdim return Base->isDefined(); 400351278Sdim } 401360784Sdim 402360784Sdim /// Returns true if this symbol is live (i.e. should be treated as a root for 403360784Sdim /// dead stripping). 404360784Sdim bool isLive() const { 405360784Sdim assert(Base && "Attempting to access null symbol"); 406360784Sdim return IsLive; 407351278Sdim } 408351278Sdim 409360784Sdim /// Set this symbol's live bit. 410360784Sdim void setLive(bool IsLive) { this->IsLive = IsLive; } 411351278Sdim 412360784Sdim /// Returns true is this symbol is callable. 413360784Sdim bool isCallable() const { return IsCallable; } 414351278Sdim 415360784Sdim /// Set this symbol's callable bit. 416360784Sdim void setCallable(bool IsCallable) { this->IsCallable = IsCallable; } 417360784Sdim 418360784Sdim /// Returns true if the underlying addressable is an unresolved external. 419360784Sdim bool isExternal() const { 420360784Sdim assert(Base && "Attempt to access null symbol"); 421360784Sdim return !Base->isDefined() && !Base->isAbsolute(); 422351278Sdim } 423351278Sdim 424360784Sdim /// Returns true if the underlying addressable is an absolute symbol. 425360784Sdim bool isAbsolute() const { 426360784Sdim assert(Base && "Attempt to access null symbol"); 427360784Sdim return !Base->isDefined() && Base->isAbsolute(); 428360784Sdim } 429351278Sdim 430360784Sdim /// Return the addressable that this symbol points to. 431360784Sdim Addressable &getAddressable() { 432360784Sdim assert(Base && "Cannot get underlying addressable for null symbol"); 433360784Sdim return *Base; 434360784Sdim } 435351278Sdim 436360784Sdim /// Return the addressable that thsi symbol points to. 437360784Sdim const Addressable &getAddressable() const { 438360784Sdim assert(Base && "Cannot get underlying addressable for null symbol"); 439360784Sdim return *Base; 440360784Sdim } 441351278Sdim 442360784Sdim /// Return the Block for this Symbol (Symbol must be defined). 443360784Sdim Block &getBlock() { 444360784Sdim assert(Base && "Cannot get block for null symbol"); 445360784Sdim assert(Base->isDefined() && "Not a defined symbol"); 446360784Sdim return static_cast<Block &>(*Base); 447360784Sdim } 448351278Sdim 449360784Sdim /// Return the Block for this Symbol (Symbol must be defined). 450360784Sdim const Block &getBlock() const { 451360784Sdim assert(Base && "Cannot get block for null symbol"); 452360784Sdim assert(Base->isDefined() && "Not a defined symbol"); 453360784Sdim return static_cast<const Block &>(*Base); 454351278Sdim } 455351278Sdim 456360784Sdim /// Returns the offset for this symbol within the underlying addressable. 457360784Sdim JITTargetAddress getOffset() const { return Offset; } 458360784Sdim 459360784Sdim /// Returns the address of this symbol. 460360784Sdim JITTargetAddress getAddress() const { return Base->getAddress() + Offset; } 461360784Sdim 462360784Sdim /// Returns the size of this symbol. 463360784Sdim JITTargetAddress getSize() const { return Size; } 464360784Sdim 465360784Sdim /// Returns true if this symbol is backed by a zero-fill block. 466360784Sdim /// This method may only be called on defined symbols. 467360784Sdim bool isSymbolZeroFill() const { return getBlock().isZeroFill(); } 468360784Sdim 469360784Sdim /// Returns the content in the underlying block covered by this symbol. 470360784Sdim /// This method may only be called on defined non-zero-fill symbols. 471360784Sdim StringRef getSymbolContent() const { 472360784Sdim return getBlock().getContent().substr(Offset, Size); 473351278Sdim } 474351278Sdim 475360784Sdim /// Get the linkage for this Symbol. 476360784Sdim Linkage getLinkage() const { return static_cast<Linkage>(L); } 477351278Sdim 478360784Sdim /// Set the linkage for this Symbol. 479360784Sdim void setLinkage(Linkage L) { 480360784Sdim assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) && 481360784Sdim "Linkage can only be applied to defined named symbols"); 482360784Sdim this->L = static_cast<uint8_t>(L); 483360784Sdim } 484351278Sdim 485360784Sdim /// Get the visibility for this Symbol. 486360784Sdim Scope getScope() const { return static_cast<Scope>(S); } 487351278Sdim 488360784Sdim /// Set the visibility for this Symbol. 489360784Sdim void setScope(Scope S) { 490360784Sdim assert((S == Scope::Default || Base->isDefined() || Base->isAbsolute()) && 491360784Sdim "Invalid visibility for symbol type"); 492360784Sdim this->S = static_cast<uint8_t>(S); 493360784Sdim } 494360784Sdim 495351278Sdimprivate: 496360784Sdim void makeExternal(Addressable &A) { 497360784Sdim assert(!A.isDefined() && "Attempting to make external with defined block"); 498360784Sdim Base = &A; 499360784Sdim Offset = 0; 500360784Sdim setLinkage(Linkage::Strong); 501360784Sdim setScope(Scope::Default); 502360784Sdim IsLive = 0; 503360784Sdim // note: Size and IsCallable fields left unchanged. 504351278Sdim } 505351278Sdim 506360784Sdim void setBlock(Block &B) { Base = &B; } 507360784Sdim 508360784Sdim void setOffset(uint64_t NewOffset) { 509360784Sdim assert(NewOffset <= MaxOffset && "Offset out of range"); 510360784Sdim Offset = NewOffset; 511351278Sdim } 512351278Sdim 513360784Sdim static constexpr uint64_t MaxOffset = (1ULL << 59) - 1; 514360784Sdim 515360784Sdim // FIXME: A char* or SymbolStringPtr may pack better. 516351278Sdim StringRef Name; 517360784Sdim Addressable *Base = nullptr; 518360784Sdim uint64_t Offset : 59; 519360784Sdim uint64_t L : 1; 520360784Sdim uint64_t S : 2; 521360784Sdim uint64_t IsLive : 1; 522360784Sdim uint64_t IsCallable : 1; 523360784Sdim JITTargetAddress Size = 0; 524351278Sdim}; 525351278Sdim 526360784Sdimraw_ostream &operator<<(raw_ostream &OS, const Symbol &A); 527351278Sdim 528360784Sdimvoid printEdge(raw_ostream &OS, const Block &B, const Edge &E, 529360784Sdim StringRef EdgeKindName); 530360784Sdim 531360784Sdim/// Represents an object file section. 532360784Sdimclass Section { 533360784Sdim friend class LinkGraph; 534360784Sdim 535351278Sdimprivate: 536360784Sdim Section(StringRef Name, sys::Memory::ProtectionFlags Prot, 537360784Sdim SectionOrdinal SecOrdinal) 538360784Sdim : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {} 539351278Sdim 540360784Sdim using SymbolSet = DenseSet<Symbol *>; 541360784Sdim using BlockSet = DenseSet<Block *>; 542351278Sdim 543351278Sdimpublic: 544360784Sdim using symbol_iterator = SymbolSet::iterator; 545360784Sdim using const_symbol_iterator = SymbolSet::const_iterator; 546351278Sdim 547360784Sdim using block_iterator = BlockSet::iterator; 548360784Sdim using const_block_iterator = BlockSet::const_iterator; 549351278Sdim 550360784Sdim ~Section(); 551351278Sdim 552360784Sdim /// Returns the name of this section. 553360784Sdim StringRef getName() const { return Name; } 554360784Sdim 555360784Sdim /// Returns the protection flags for this section. 556360784Sdim sys::Memory::ProtectionFlags getProtectionFlags() const { return Prot; } 557360784Sdim 558360784Sdim /// Returns the ordinal for this section. 559360784Sdim SectionOrdinal getOrdinal() const { return SecOrdinal; } 560360784Sdim 561360784Sdim /// Returns an iterator over the blocks defined in this section. 562360784Sdim iterator_range<block_iterator> blocks() { 563360784Sdim return make_range(Blocks.begin(), Blocks.end()); 564351278Sdim } 565360784Sdim 566360784Sdim /// Returns an iterator over the blocks defined in this section. 567360784Sdim iterator_range<const_block_iterator> blocks() const { 568360784Sdim return make_range(Blocks.begin(), Blocks.end()); 569351278Sdim } 570351278Sdim 571360784Sdim /// Returns an iterator over the symbols defined in this section. 572360784Sdim iterator_range<symbol_iterator> symbols() { 573360784Sdim return make_range(Symbols.begin(), Symbols.end()); 574351278Sdim } 575351278Sdim 576360784Sdim /// Returns an iterator over the symbols defined in this section. 577360784Sdim iterator_range<const_symbol_iterator> symbols() const { 578360784Sdim return make_range(Symbols.begin(), Symbols.end()); 579351278Sdim } 580351278Sdim 581360784Sdim /// Return the number of symbols in this section. 582360784Sdim SymbolSet::size_type symbols_size() { return Symbols.size(); } 583351278Sdim 584360784Sdimprivate: 585360784Sdim void addSymbol(Symbol &Sym) { 586360784Sdim assert(!Symbols.count(&Sym) && "Symbol is already in this section"); 587360784Sdim Symbols.insert(&Sym); 588351278Sdim } 589360784Sdim 590360784Sdim void removeSymbol(Symbol &Sym) { 591360784Sdim assert(Symbols.count(&Sym) && "symbol is not in this section"); 592360784Sdim Symbols.erase(&Sym); 593351278Sdim } 594351278Sdim 595360784Sdim void addBlock(Block &B) { 596360784Sdim assert(!Blocks.count(&B) && "Block is already in this section"); 597360784Sdim Blocks.insert(&B); 598360784Sdim } 599351278Sdim 600360784Sdim void removeBlock(Block &B) { 601360784Sdim assert(Blocks.count(&B) && "Block is not in this section"); 602360784Sdim Blocks.erase(&B); 603351278Sdim } 604351278Sdim 605360784Sdim StringRef Name; 606360784Sdim sys::Memory::ProtectionFlags Prot; 607360784Sdim SectionOrdinal SecOrdinal = 0; 608360784Sdim BlockSet Blocks; 609360784Sdim SymbolSet Symbols; 610360784Sdim}; 611360784Sdim 612360784Sdim/// Represents a section address range via a pair of Block pointers 613360784Sdim/// to the first and last Blocks in the section. 614360784Sdimclass SectionRange { 615360784Sdimpublic: 616360784Sdim SectionRange() = default; 617360784Sdim SectionRange(const Section &Sec) { 618360784Sdim if (llvm::empty(Sec.blocks())) 619360784Sdim return; 620360784Sdim First = Last = *Sec.blocks().begin(); 621360784Sdim for (auto *B : Sec.blocks()) { 622360784Sdim if (B->getAddress() < First->getAddress()) 623360784Sdim First = B; 624360784Sdim if (B->getAddress() > Last->getAddress()) 625360784Sdim Last = B; 626360784Sdim } 627351278Sdim } 628360784Sdim Block *getFirstBlock() const { 629360784Sdim assert((!Last || First) && "First can not be null if end is non-null"); 630360784Sdim return First; 631360784Sdim } 632360784Sdim Block *getLastBlock() const { 633360784Sdim assert((First || !Last) && "Last can not be null if start is non-null"); 634360784Sdim return Last; 635360784Sdim } 636360784Sdim bool isEmpty() const { 637360784Sdim assert((First || !Last) && "Last can not be null if start is non-null"); 638360784Sdim return !First; 639360784Sdim } 640360784Sdim JITTargetAddress getStart() const { 641360784Sdim return First ? First->getAddress() : 0; 642360784Sdim } 643360784Sdim JITTargetAddress getEnd() const { 644360784Sdim return Last ? Last->getAddress() + Last->getSize() : 0; 645360784Sdim } 646360784Sdim uint64_t getSize() const { return getEnd() - getStart(); } 647351278Sdim 648360784Sdimprivate: 649360784Sdim Block *First = nullptr; 650360784Sdim Block *Last = nullptr; 651360784Sdim}; 652351278Sdim 653360784Sdimclass LinkGraph { 654351278Sdimprivate: 655360784Sdim using SectionList = std::vector<std::unique_ptr<Section>>; 656360784Sdim using ExternalSymbolSet = DenseSet<Symbol *>; 657360784Sdim using BlockSet = DenseSet<Block *>; 658360784Sdim 659360784Sdim template <typename... ArgTs> 660360784Sdim Addressable &createAddressable(ArgTs &&... Args) { 661360784Sdim Addressable *A = 662360784Sdim reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>()); 663360784Sdim new (A) Addressable(std::forward<ArgTs>(Args)...); 664360784Sdim return *A; 665351278Sdim } 666351278Sdim 667360784Sdim void destroyAddressable(Addressable &A) { 668360784Sdim A.~Addressable(); 669360784Sdim Allocator.Deallocate(&A); 670360784Sdim } 671351278Sdim 672360784Sdim template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) { 673360784Sdim Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>()); 674360784Sdim new (B) Block(std::forward<ArgTs>(Args)...); 675360784Sdim B->getSection().addBlock(*B); 676360784Sdim return *B; 677360784Sdim } 678351278Sdim 679360784Sdim void destroyBlock(Block &B) { 680360784Sdim B.~Block(); 681360784Sdim Allocator.Deallocate(&B); 682360784Sdim } 683351278Sdim 684360784Sdim void destroySymbol(Symbol &S) { 685360784Sdim S.~Symbol(); 686360784Sdim Allocator.Deallocate(&S); 687360784Sdim } 688351278Sdim 689360784Sdim static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) { 690360784Sdim return S.blocks(); 691351278Sdim } 692351278Sdim 693360784Sdim static iterator_range<Section::const_block_iterator> 694360784Sdim getSectionConstBlocks(Section &S) { 695360784Sdim return S.blocks(); 696360784Sdim } 697351278Sdim 698360784Sdim static iterator_range<Section::symbol_iterator> 699360784Sdim getSectionSymbols(Section &S) { 700360784Sdim return S.symbols(); 701360784Sdim } 702360784Sdim 703360784Sdim static iterator_range<Section::const_symbol_iterator> 704360784Sdim getSectionConstSymbols(Section &S) { 705360784Sdim return S.symbols(); 706360784Sdim } 707360784Sdim 708351278Sdimpublic: 709360784Sdim using external_symbol_iterator = ExternalSymbolSet::iterator; 710351278Sdim 711351278Sdim using section_iterator = pointee_iterator<SectionList::iterator>; 712351278Sdim using const_section_iterator = pointee_iterator<SectionList::const_iterator>; 713351278Sdim 714360784Sdim template <typename OuterItrT, typename InnerItrT, typename T, 715360784Sdim iterator_range<InnerItrT> getInnerRange( 716360784Sdim typename OuterItrT::reference)> 717360784Sdim class nested_collection_iterator 718351278Sdim : public iterator_facade_base< 719360784Sdim nested_collection_iterator<OuterItrT, InnerItrT, T, getInnerRange>, 720351278Sdim std::forward_iterator_tag, T> { 721351278Sdim public: 722360784Sdim nested_collection_iterator() = default; 723351278Sdim 724360784Sdim nested_collection_iterator(OuterItrT OuterI, OuterItrT OuterE) 725360784Sdim : OuterI(OuterI), OuterE(OuterE), 726360784Sdim InnerI(getInnerBegin(OuterI, OuterE)) { 727360784Sdim moveToNonEmptyInnerOrEnd(); 728351278Sdim } 729351278Sdim 730360784Sdim bool operator==(const nested_collection_iterator &RHS) const { 731360784Sdim return (OuterI == RHS.OuterI) && (InnerI == RHS.InnerI); 732351278Sdim } 733351278Sdim 734351278Sdim T operator*() const { 735360784Sdim assert(InnerI != getInnerRange(*OuterI).end() && "Dereferencing end?"); 736360784Sdim return *InnerI; 737351278Sdim } 738351278Sdim 739360784Sdim nested_collection_iterator operator++() { 740360784Sdim ++InnerI; 741360784Sdim moveToNonEmptyInnerOrEnd(); 742351278Sdim return *this; 743351278Sdim } 744351278Sdim 745351278Sdim private: 746360784Sdim static InnerItrT getInnerBegin(OuterItrT OuterI, OuterItrT OuterE) { 747360784Sdim return OuterI != OuterE ? getInnerRange(*OuterI).begin() : InnerItrT(); 748360784Sdim } 749360784Sdim 750360784Sdim void moveToNonEmptyInnerOrEnd() { 751360784Sdim while (OuterI != OuterE && InnerI == getInnerRange(*OuterI).end()) { 752360784Sdim ++OuterI; 753360784Sdim InnerI = getInnerBegin(OuterI, OuterE); 754351278Sdim } 755351278Sdim } 756351278Sdim 757360784Sdim OuterItrT OuterI, OuterE; 758360784Sdim InnerItrT InnerI; 759351278Sdim }; 760351278Sdim 761360784Sdim using defined_symbol_iterator = 762360784Sdim nested_collection_iterator<const_section_iterator, 763360784Sdim Section::symbol_iterator, Symbol *, 764360784Sdim getSectionSymbols>; 765351278Sdim 766360784Sdim using const_defined_symbol_iterator = 767360784Sdim nested_collection_iterator<const_section_iterator, 768360784Sdim Section::const_symbol_iterator, const Symbol *, 769360784Sdim getSectionConstSymbols>; 770351278Sdim 771360784Sdim using block_iterator = nested_collection_iterator<const_section_iterator, 772360784Sdim Section::block_iterator, 773360784Sdim Block *, getSectionBlocks>; 774360784Sdim 775360784Sdim using const_block_iterator = 776360784Sdim nested_collection_iterator<const_section_iterator, 777360784Sdim Section::const_block_iterator, const Block *, 778360784Sdim getSectionConstBlocks>; 779360784Sdim 780360784Sdim LinkGraph(std::string Name, unsigned PointerSize, 781351278Sdim support::endianness Endianness) 782351278Sdim : Name(std::move(Name)), PointerSize(PointerSize), 783351278Sdim Endianness(Endianness) {} 784351278Sdim 785351278Sdim /// Returns the name of this graph (usually the name of the original 786351278Sdim /// underlying MemoryBuffer). 787351278Sdim const std::string &getName() { return Name; } 788351278Sdim 789351278Sdim /// Returns the pointer size for use in this graph. 790351278Sdim unsigned getPointerSize() const { return PointerSize; } 791351278Sdim 792360784Sdim /// Returns the endianness of content in this graph. 793351278Sdim support::endianness getEndianness() const { return Endianness; } 794351278Sdim 795351278Sdim /// Create a section with the given name, protection flags, and alignment. 796360784Sdim Section &createSection(StringRef Name, sys::Memory::ProtectionFlags Prot) { 797360784Sdim std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size())); 798351278Sdim Sections.push_back(std::move(Sec)); 799351278Sdim return *Sections.back(); 800351278Sdim } 801351278Sdim 802360784Sdim /// Create a content block. 803360784Sdim Block &createContentBlock(Section &Parent, StringRef Content, 804360784Sdim uint64_t Address, uint64_t Alignment, 805360784Sdim uint64_t AlignmentOffset) { 806360784Sdim return createBlock(Parent, Content, Address, Alignment, AlignmentOffset); 807351278Sdim } 808351278Sdim 809360784Sdim /// Create a zero-fill block. 810360784Sdim Block &createZeroFillBlock(Section &Parent, uint64_t Size, uint64_t Address, 811360784Sdim uint64_t Alignment, uint64_t AlignmentOffset) { 812360784Sdim return createBlock(Parent, Size, Address, Alignment, AlignmentOffset); 813351278Sdim } 814351278Sdim 815360784Sdim /// Cache type for the splitBlock function. 816360784Sdim using SplitBlockCache = Optional<SmallVector<Symbol *, 8>>; 817360784Sdim 818360784Sdim /// Splits block B at the given index which must be greater than zero. 819360784Sdim /// If SplitIndex == B.getSize() then this function is a no-op and returns B. 820360784Sdim /// If SplitIndex < B.getSize() then this function returns a new block 821360784Sdim /// covering the range [ 0, SplitIndex ), and B is modified to cover the range 822360784Sdim /// [ SplitIndex, B.size() ). 823351278Sdim /// 824360784Sdim /// The optional Cache parameter can be used to speed up repeated calls to 825360784Sdim /// splitBlock for a single block. If the value is None the cache will be 826360784Sdim /// treated as uninitialized and splitBlock will populate it. Otherwise it 827360784Sdim /// is assumed to contain the list of Symbols pointing at B, sorted in 828360784Sdim /// descending order of offset. 829360784Sdim /// 830360784Sdim /// Notes: 831360784Sdim /// 832360784Sdim /// 1. The newly introduced block will have a new ordinal which will be 833360784Sdim /// higher than any other ordinals in the section. Clients are responsible 834360784Sdim /// for re-assigning block ordinals to restore a compatible order if 835360784Sdim /// needed. 836360784Sdim /// 837360784Sdim /// 2. The cache is not automatically updated if new symbols are introduced 838360784Sdim /// between calls to splitBlock. Any newly introduced symbols may be 839360784Sdim /// added to the cache manually (descending offset order must be 840360784Sdim /// preserved), or the cache can be set to None and rebuilt by 841360784Sdim /// splitBlock on the next call. 842360784Sdim Block &splitBlock(Block &B, size_t SplitIndex, 843360784Sdim SplitBlockCache *Cache = nullptr); 844360784Sdim 845360784Sdim /// Add an external symbol. 846360784Sdim /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose 847360784Sdim /// size is not known, you should substitute '0'. 848360784Sdim /// For external symbols Linkage determines whether the symbol must be 849360784Sdim /// present during lookup: Externals with strong linkage must be found or 850360784Sdim /// an error will be emitted. Externals with weak linkage are permitted to 851360784Sdim /// be undefined, in which case they are assigned a value of 0. 852360784Sdim Symbol &addExternalSymbol(StringRef Name, uint64_t Size, Linkage L) { 853360784Sdim auto &Sym = 854360784Sdim Symbol::constructExternal(Allocator.Allocate<Symbol>(), 855360784Sdim createAddressable(0, false), Name, Size, L); 856360784Sdim ExternalSymbols.insert(&Sym); 857360784Sdim return Sym; 858351278Sdim } 859351278Sdim 860360784Sdim /// Add an absolute symbol. 861360784Sdim Symbol &addAbsoluteSymbol(StringRef Name, JITTargetAddress Address, 862360784Sdim uint64_t Size, Linkage L, Scope S, bool IsLive) { 863360784Sdim auto &Sym = Symbol::constructAbsolute(Allocator.Allocate<Symbol>(), 864360784Sdim createAddressable(Address), Name, 865360784Sdim Size, L, S, IsLive); 866360784Sdim AbsoluteSymbols.insert(&Sym); 867360784Sdim return Sym; 868351278Sdim } 869351278Sdim 870360784Sdim /// Convenience method for adding a weak zero-fill symbol. 871360784Sdim Symbol &addCommonSymbol(StringRef Name, Scope S, Section &Section, 872360784Sdim JITTargetAddress Address, uint64_t Size, 873360784Sdim uint64_t Alignment, bool IsLive) { 874360784Sdim auto &Sym = Symbol::constructCommon( 875360784Sdim Allocator.Allocate<Symbol>(), 876360784Sdim createBlock(Section, Size, Address, Alignment, 0), Name, Size, S, 877360784Sdim IsLive); 878360784Sdim Section.addSymbol(Sym); 879360784Sdim return Sym; 880351278Sdim } 881351278Sdim 882360784Sdim /// Add an anonymous symbol. 883360784Sdim Symbol &addAnonymousSymbol(Block &Content, JITTargetAddress Offset, 884360784Sdim JITTargetAddress Size, bool IsCallable, 885360784Sdim bool IsLive) { 886360784Sdim auto &Sym = Symbol::constructAnonDef(Allocator.Allocate<Symbol>(), Content, 887360784Sdim Offset, Size, IsCallable, IsLive); 888360784Sdim Content.getSection().addSymbol(Sym); 889360784Sdim return Sym; 890360784Sdim } 891360784Sdim 892360784Sdim /// Add a named symbol. 893360784Sdim Symbol &addDefinedSymbol(Block &Content, JITTargetAddress Offset, 894360784Sdim StringRef Name, JITTargetAddress Size, Linkage L, 895360784Sdim Scope S, bool IsCallable, bool IsLive) { 896360784Sdim auto &Sym = 897360784Sdim Symbol::constructNamedDef(Allocator.Allocate<Symbol>(), Content, Offset, 898360784Sdim Name, Size, L, S, IsLive, IsCallable); 899360784Sdim Content.getSection().addSymbol(Sym); 900360784Sdim return Sym; 901360784Sdim } 902360784Sdim 903351278Sdim iterator_range<section_iterator> sections() { 904351278Sdim return make_range(section_iterator(Sections.begin()), 905351278Sdim section_iterator(Sections.end())); 906351278Sdim } 907351278Sdim 908351278Sdim /// Returns the section with the given name if it exists, otherwise returns 909351278Sdim /// null. 910351278Sdim Section *findSectionByName(StringRef Name) { 911351278Sdim for (auto &S : sections()) 912351278Sdim if (S.getName() == Name) 913351278Sdim return &S; 914351278Sdim return nullptr; 915351278Sdim } 916351278Sdim 917360784Sdim iterator_range<block_iterator> blocks() { 918360784Sdim return make_range(block_iterator(Sections.begin(), Sections.end()), 919360784Sdim block_iterator(Sections.end(), Sections.end())); 920351278Sdim } 921351278Sdim 922360784Sdim iterator_range<const_block_iterator> blocks() const { 923360784Sdim return make_range(const_block_iterator(Sections.begin(), Sections.end()), 924360784Sdim const_block_iterator(Sections.end(), Sections.end())); 925351278Sdim } 926351278Sdim 927360784Sdim iterator_range<external_symbol_iterator> external_symbols() { 928360784Sdim return make_range(ExternalSymbols.begin(), ExternalSymbols.end()); 929351278Sdim } 930351278Sdim 931360784Sdim iterator_range<external_symbol_iterator> absolute_symbols() { 932360784Sdim return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end()); 933360784Sdim } 934360784Sdim 935360784Sdim iterator_range<defined_symbol_iterator> defined_symbols() { 936360784Sdim return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()), 937360784Sdim defined_symbol_iterator(Sections.end(), Sections.end())); 938360784Sdim } 939360784Sdim 940360784Sdim iterator_range<const_defined_symbol_iterator> defined_symbols() const { 941351278Sdim return make_range( 942360784Sdim const_defined_symbol_iterator(Sections.begin(), Sections.end()), 943360784Sdim const_defined_symbol_iterator(Sections.end(), Sections.end())); 944351278Sdim } 945351278Sdim 946360784Sdim /// Turn a defined symbol into an external one. 947360784Sdim void makeExternal(Symbol &Sym) { 948360784Sdim if (Sym.getAddressable().isAbsolute()) { 949360784Sdim assert(AbsoluteSymbols.count(&Sym) && 950360784Sdim "Sym is not in the absolute symbols set"); 951360784Sdim AbsoluteSymbols.erase(&Sym); 952360784Sdim } else { 953360784Sdim assert(Sym.isDefined() && "Sym is not a defined symbol"); 954360784Sdim Section &Sec = Sym.getBlock().getSection(); 955360784Sdim Sec.removeSymbol(Sym); 956360784Sdim } 957360784Sdim Sym.makeExternal(createAddressable(false)); 958360784Sdim ExternalSymbols.insert(&Sym); 959351278Sdim } 960351278Sdim 961360784Sdim /// Removes an external symbol. Also removes the underlying Addressable. 962360784Sdim void removeExternalSymbol(Symbol &Sym) { 963360784Sdim assert(!Sym.isDefined() && !Sym.isAbsolute() && 964360784Sdim "Sym is not an external symbol"); 965360784Sdim assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set"); 966360784Sdim ExternalSymbols.erase(&Sym); 967360784Sdim Addressable &Base = *Sym.Base; 968360784Sdim destroySymbol(Sym); 969360784Sdim destroyAddressable(Base); 970351278Sdim } 971351278Sdim 972360784Sdim /// Remove an absolute symbol. Also removes the underlying Addressable. 973360784Sdim void removeAbsoluteSymbol(Symbol &Sym) { 974360784Sdim assert(!Sym.isDefined() && Sym.isAbsolute() && 975360784Sdim "Sym is not an absolute symbol"); 976360784Sdim assert(AbsoluteSymbols.count(&Sym) && 977360784Sdim "Symbol is not in the absolute symbols set"); 978360784Sdim AbsoluteSymbols.erase(&Sym); 979360784Sdim Addressable &Base = *Sym.Base; 980360784Sdim destroySymbol(Sym); 981360784Sdim destroyAddressable(Base); 982351278Sdim } 983351278Sdim 984360784Sdim /// Removes defined symbols. Does not remove the underlying block. 985360784Sdim void removeDefinedSymbol(Symbol &Sym) { 986360784Sdim assert(Sym.isDefined() && "Sym is not a defined symbol"); 987360784Sdim Sym.getBlock().getSection().removeSymbol(Sym); 988360784Sdim destroySymbol(Sym); 989351278Sdim } 990351278Sdim 991360784Sdim /// Remove a block. 992360784Sdim void removeBlock(Block &B) { 993360784Sdim B.getSection().removeBlock(B); 994360784Sdim destroyBlock(B); 995360784Sdim } 996360784Sdim 997360784Sdim /// Dump the graph. 998351278Sdim /// 999360784Sdim /// If supplied, the EdgeKindToName function will be used to name edge 1000360784Sdim /// kinds in the debug output. Otherwise raw edge kind numbers will be 1001360784Sdim /// displayed. 1002360784Sdim void dump(raw_ostream &OS, 1003360784Sdim std::function<StringRef(Edge::Kind)> EdegKindToName = 1004360784Sdim std::function<StringRef(Edge::Kind)>()); 1005351278Sdim 1006360784Sdimprivate: 1007360784Sdim // Put the BumpPtrAllocator first so that we don't free any of the underlying 1008360784Sdim // memory until the Symbol/Addressable destructors have been run. 1009360784Sdim BumpPtrAllocator Allocator; 1010351278Sdim 1011360784Sdim std::string Name; 1012360784Sdim unsigned PointerSize; 1013360784Sdim support::endianness Endianness; 1014360784Sdim SectionList Sections; 1015360784Sdim ExternalSymbolSet ExternalSymbols; 1016360784Sdim ExternalSymbolSet AbsoluteSymbols; 1017360784Sdim}; 1018351278Sdim 1019360784Sdim/// Enables easy lookup of blocks by addresses. 1020360784Sdimclass BlockAddressMap { 1021360784Sdimpublic: 1022360784Sdim using AddrToBlockMap = std::map<JITTargetAddress, Block *>; 1023360784Sdim using const_iterator = AddrToBlockMap::const_iterator; 1024351278Sdim 1025360784Sdim /// A block predicate that always adds all blocks. 1026360784Sdim static bool includeAllBlocks(const Block &B) { return true; } 1027351278Sdim 1028360784Sdim /// A block predicate that always includes blocks with non-null addresses. 1029360784Sdim static bool includeNonNull(const Block &B) { return B.getAddress(); } 1030351278Sdim 1031360784Sdim BlockAddressMap() = default; 1032360784Sdim 1033360784Sdim /// Add a block to the map. Returns an error if the block overlaps with any 1034360784Sdim /// existing block. 1035360784Sdim template <typename PredFn = decltype(includeAllBlocks)> 1036360784Sdim Error addBlock(Block &B, PredFn Pred = includeAllBlocks) { 1037360784Sdim if (!Pred(B)) 1038360784Sdim return Error::success(); 1039360784Sdim 1040360784Sdim auto I = AddrToBlock.upper_bound(B.getAddress()); 1041360784Sdim 1042360784Sdim // If we're not at the end of the map, check for overlap with the next 1043360784Sdim // element. 1044360784Sdim if (I != AddrToBlock.end()) { 1045360784Sdim if (B.getAddress() + B.getSize() > I->second->getAddress()) 1046360784Sdim return overlapError(B, *I->second); 1047360784Sdim } 1048360784Sdim 1049360784Sdim // If we're not at the start of the map, check for overlap with the previous 1050360784Sdim // element. 1051360784Sdim if (I != AddrToBlock.begin()) { 1052360784Sdim auto &PrevBlock = *std::prev(I)->second; 1053360784Sdim if (PrevBlock.getAddress() + PrevBlock.getSize() > B.getAddress()) 1054360784Sdim return overlapError(B, PrevBlock); 1055360784Sdim } 1056360784Sdim 1057360784Sdim AddrToBlock.insert(I, std::make_pair(B.getAddress(), &B)); 1058360784Sdim return Error::success(); 1059351278Sdim } 1060351278Sdim 1061360784Sdim /// Add a block to the map without checking for overlap with existing blocks. 1062360784Sdim /// The client is responsible for ensuring that the block added does not 1063360784Sdim /// overlap with any existing block. 1064360784Sdim void addBlockWithoutChecking(Block &B) { AddrToBlock[B.getAddress()] = &B; } 1065360784Sdim 1066360784Sdim /// Add a range of blocks to the map. Returns an error if any block in the 1067360784Sdim /// range overlaps with any other block in the range, or with any existing 1068360784Sdim /// block in the map. 1069360784Sdim template <typename BlockPtrRange, 1070360784Sdim typename PredFn = decltype(includeAllBlocks)> 1071360784Sdim Error addBlocks(BlockPtrRange &&Blocks, PredFn Pred = includeAllBlocks) { 1072360784Sdim for (auto *B : Blocks) 1073360784Sdim if (auto Err = addBlock(*B, Pred)) 1074360784Sdim return Err; 1075360784Sdim return Error::success(); 1076351278Sdim } 1077351278Sdim 1078360784Sdim /// Add a range of blocks to the map without checking for overlap with 1079360784Sdim /// existing blocks. The client is responsible for ensuring that the block 1080360784Sdim /// added does not overlap with any existing block. 1081360784Sdim template <typename BlockPtrRange> 1082360784Sdim void addBlocksWithoutChecking(BlockPtrRange &&Blocks) { 1083360784Sdim for (auto *B : Blocks) 1084360784Sdim addBlockWithoutChecking(*B); 1085351278Sdim } 1086351278Sdim 1087360784Sdim /// Iterates over (Address, Block*) pairs in ascending order of address. 1088360784Sdim const_iterator begin() const { return AddrToBlock.begin(); } 1089360784Sdim const_iterator end() const { return AddrToBlock.end(); } 1090360784Sdim 1091360784Sdim /// Returns the block starting at the given address, or nullptr if no such 1092360784Sdim /// block exists. 1093360784Sdim Block *getBlockAt(JITTargetAddress Addr) const { 1094360784Sdim auto I = AddrToBlock.find(Addr); 1095360784Sdim if (I == AddrToBlock.end()) 1096360784Sdim return nullptr; 1097360784Sdim return I->second; 1098351278Sdim } 1099351278Sdim 1100360784Sdim /// Returns the block covering the given address, or nullptr if no such block 1101360784Sdim /// exists. 1102360784Sdim Block *getBlockCovering(JITTargetAddress Addr) const { 1103360784Sdim auto I = AddrToBlock.upper_bound(Addr); 1104360784Sdim if (I == AddrToBlock.begin()) 1105360784Sdim return nullptr; 1106360784Sdim auto *B = std::prev(I)->second; 1107360784Sdim if (Addr < B->getAddress() + B->getSize()) 1108360784Sdim return B; 1109360784Sdim return nullptr; 1110351278Sdim } 1111351278Sdim 1112360784Sdimprivate: 1113360784Sdim Error overlapError(Block &NewBlock, Block &ExistingBlock) { 1114360784Sdim auto NewBlockEnd = NewBlock.getAddress() + NewBlock.getSize(); 1115360784Sdim auto ExistingBlockEnd = 1116360784Sdim ExistingBlock.getAddress() + ExistingBlock.getSize(); 1117360784Sdim return make_error<JITLinkError>( 1118360784Sdim "Block at " + 1119360784Sdim formatv("{0:x16} -- {1:x16}", NewBlock.getAddress(), NewBlockEnd) + 1120360784Sdim " overlaps " + 1121360784Sdim formatv("{0:x16} -- {1:x16}", ExistingBlock.getAddress(), 1122360784Sdim ExistingBlockEnd)); 1123360784Sdim } 1124351278Sdim 1125360784Sdim AddrToBlockMap AddrToBlock; 1126360784Sdim}; 1127351278Sdim 1128360784Sdim/// A map of addresses to Symbols. 1129360784Sdimclass SymbolAddressMap { 1130360784Sdimpublic: 1131360784Sdim using SymbolVector = SmallVector<Symbol *, 1>; 1132360784Sdim 1133360784Sdim /// Add a symbol to the SymbolAddressMap. 1134360784Sdim void addSymbol(Symbol &Sym) { 1135360784Sdim AddrToSymbols[Sym.getAddress()].push_back(&Sym); 1136351278Sdim } 1137351278Sdim 1138360784Sdim /// Add all symbols in a given range to the SymbolAddressMap. 1139360784Sdim template <typename SymbolPtrCollection> 1140360784Sdim void addSymbols(SymbolPtrCollection &&Symbols) { 1141360784Sdim for (auto *Sym : Symbols) 1142360784Sdim addSymbol(*Sym); 1143351278Sdim } 1144351278Sdim 1145360784Sdim /// Returns the list of symbols that start at the given address, or nullptr if 1146360784Sdim /// no such symbols exist. 1147360784Sdim const SymbolVector *getSymbolsAt(JITTargetAddress Addr) const { 1148360784Sdim auto I = AddrToSymbols.find(Addr); 1149360784Sdim if (I == AddrToSymbols.end()) 1150360784Sdim return nullptr; 1151360784Sdim return &I->second; 1152351278Sdim } 1153351278Sdim 1154360784Sdimprivate: 1155360784Sdim std::map<JITTargetAddress, SymbolVector> AddrToSymbols; 1156351278Sdim}; 1157351278Sdim 1158360784Sdim/// A function for mutating LinkGraphs. 1159360784Sdimusing LinkGraphPassFunction = std::function<Error(LinkGraph &)>; 1160351278Sdim 1161360784Sdim/// A list of LinkGraph passes. 1162360784Sdimusing LinkGraphPassList = std::vector<LinkGraphPassFunction>; 1163351278Sdim 1164360784Sdim/// An LinkGraph pass configuration, consisting of a list of pre-prune, 1165351278Sdim/// post-prune, and post-fixup passes. 1166351278Sdimstruct PassConfiguration { 1167351278Sdim 1168351278Sdim /// Pre-prune passes. 1169351278Sdim /// 1170351278Sdim /// These passes are called on the graph after it is built, and before any 1171360784Sdim /// symbols have been pruned. 1172351278Sdim /// 1173360784Sdim /// Notable use cases: Marking symbols live or should-discard. 1174360784Sdim LinkGraphPassList PrePrunePasses; 1175351278Sdim 1176351278Sdim /// Post-prune passes. 1177351278Sdim /// 1178360784Sdim /// These passes are called on the graph after dead stripping, but before 1179360784Sdim /// fixups are applied. 1180351278Sdim /// 1181360784Sdim /// Notable use cases: Building GOT, stub, and TLV symbols. 1182360784Sdim LinkGraphPassList PostPrunePasses; 1183351278Sdim 1184351278Sdim /// Post-fixup passes. 1185351278Sdim /// 1186360784Sdim /// These passes are called on the graph after block contents has been copied 1187351278Sdim /// to working memory, and fixups applied. 1188351278Sdim /// 1189351278Sdim /// Notable use cases: Testing and validation. 1190360784Sdim LinkGraphPassList PostFixupPasses; 1191351278Sdim}; 1192351278Sdim 1193360784Sdim/// Flags for symbol lookup. 1194360784Sdim/// 1195360784Sdim/// FIXME: These basically duplicate orc::SymbolLookupFlags -- We should merge 1196360784Sdim/// the two types once we have an OrcSupport library. 1197360784Sdimenum class SymbolLookupFlags { RequiredSymbol, WeaklyReferencedSymbol }; 1198360784Sdim 1199360784Sdimraw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF); 1200360784Sdim 1201351278Sdim/// A map of symbol names to resolved addresses. 1202351278Sdimusing AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>; 1203351278Sdim 1204360784Sdim/// A function object to call with a resolved symbol map (See AsyncLookupResult) 1205360784Sdim/// or an error if resolution failed. 1206360784Sdimclass JITLinkAsyncLookupContinuation { 1207360784Sdimpublic: 1208360784Sdim virtual ~JITLinkAsyncLookupContinuation() {} 1209360784Sdim virtual void run(Expected<AsyncLookupResult> LR) = 0; 1210351278Sdim 1211360784Sdimprivate: 1212360784Sdim virtual void anchor(); 1213360784Sdim}; 1214351278Sdim 1215360784Sdim/// Create a lookup continuation from a function object. 1216360784Sdimtemplate <typename Continuation> 1217360784Sdimstd::unique_ptr<JITLinkAsyncLookupContinuation> 1218360784SdimcreateLookupContinuation(Continuation Cont) { 1219360784Sdim 1220360784Sdim class Impl final : public JITLinkAsyncLookupContinuation { 1221360784Sdim public: 1222360784Sdim Impl(Continuation C) : C(std::move(C)) {} 1223360784Sdim void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); } 1224360784Sdim 1225360784Sdim private: 1226360784Sdim Continuation C; 1227360784Sdim }; 1228360784Sdim 1229360784Sdim return std::make_unique<Impl>(std::move(Cont)); 1230360784Sdim} 1231360784Sdim 1232351278Sdim/// Holds context for a single jitLink invocation. 1233351278Sdimclass JITLinkContext { 1234351278Sdimpublic: 1235360784Sdim using LookupMap = DenseMap<StringRef, SymbolLookupFlags>; 1236360784Sdim 1237351278Sdim /// Destroy a JITLinkContext. 1238351278Sdim virtual ~JITLinkContext(); 1239351278Sdim 1240351278Sdim /// Return the MemoryManager to be used for this link. 1241351278Sdim virtual JITLinkMemoryManager &getMemoryManager() = 0; 1242351278Sdim 1243351278Sdim /// Returns a StringRef for the object buffer. 1244351278Sdim /// This method can not be called once takeObjectBuffer has been called. 1245351278Sdim virtual MemoryBufferRef getObjectBuffer() const = 0; 1246351278Sdim 1247351278Sdim /// Notify this context that linking failed. 1248351278Sdim /// Called by JITLink if linking cannot be completed. 1249351278Sdim virtual void notifyFailed(Error Err) = 0; 1250351278Sdim 1251351278Sdim /// Called by JITLink to resolve external symbols. This method is passed a 1252351278Sdim /// lookup continutation which it must call with a result to continue the 1253351278Sdim /// linking process. 1254360784Sdim virtual void lookup(const LookupMap &Symbols, 1255360784Sdim std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0; 1256351278Sdim 1257360784Sdim /// Called by JITLink once all defined symbols in the graph have been assigned 1258360784Sdim /// their final memory locations in the target process. At this point the 1259360784Sdim /// LinkGraph can be inspected to build a symbol table, however the block 1260351278Sdim /// content will not generally have been copied to the target location yet. 1261360784Sdim virtual void notifyResolved(LinkGraph &G) = 0; 1262351278Sdim 1263351278Sdim /// Called by JITLink to notify the context that the object has been 1264351278Sdim /// finalized (i.e. emitted to memory and memory permissions set). If all of 1265351278Sdim /// this objects dependencies have also been finalized then the code is ready 1266351278Sdim /// to run. 1267351278Sdim virtual void 1268351278Sdim notifyFinalized(std::unique_ptr<JITLinkMemoryManager::Allocation> A) = 0; 1269351278Sdim 1270351278Sdim /// Called by JITLink prior to linking to determine whether default passes for 1271351278Sdim /// the target should be added. The default implementation returns true. 1272351278Sdim /// If subclasses override this method to return false for any target then 1273351278Sdim /// they are required to fully configure the pass pipeline for that target. 1274351278Sdim virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const; 1275351278Sdim 1276351278Sdim /// Returns the mark-live pass to be used for this link. If no pass is 1277351278Sdim /// returned (the default) then the target-specific linker implementation will 1278360784Sdim /// choose a conservative default (usually marking all symbols live). 1279351278Sdim /// This function is only called if shouldAddDefaultTargetPasses returns true, 1280351278Sdim /// otherwise the JITContext is responsible for adding a mark-live pass in 1281351278Sdim /// modifyPassConfig. 1282360784Sdim virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const; 1283351278Sdim 1284351278Sdim /// Called by JITLink to modify the pass pipeline prior to linking. 1285351278Sdim /// The default version performs no modification. 1286351278Sdim virtual Error modifyPassConfig(const Triple &TT, PassConfiguration &Config); 1287351278Sdim}; 1288351278Sdim 1289360784Sdim/// Marks all symbols in a graph live. This can be used as a default, 1290360784Sdim/// conservative mark-live implementation. 1291360784SdimError markAllSymbolsLive(LinkGraph &G); 1292351278Sdim 1293351278Sdim/// Basic JITLink implementation. 1294351278Sdim/// 1295351278Sdim/// This function will use sensible defaults for GOT and Stub handling. 1296351278Sdimvoid jitLink(std::unique_ptr<JITLinkContext> Ctx); 1297351278Sdim 1298351278Sdim} // end namespace jitlink 1299351278Sdim} // end namespace llvm 1300351278Sdim 1301351278Sdim#endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H 1302