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