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