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