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