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