diff --git a/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h b/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h --- a/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h +++ b/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h @@ -385,6 +385,79 @@ raw_ostream &operator<<(raw_ostream &OS, const Block &B); +/// When applying an operation to a symbol, this policy describes how the +/// operation should be applied to any aliases of the symbol. +enum class AliasOperationPolicy { + /// Apply the operation to all aliases in the subtree rooted at the given + /// symbol (i.e. all transitive aliases of the given symbol). + /// + /// You should generally use the 'SubTree' policy where all of the following + /// conditions hold: + /// (1) You're applying the operation to one specific Symbol (e.g. one + /// identified by name), rather than to all symbols that satisfy a + /// generic predicate (e.g. "is in section X"), + /// (2) You know that the given symbol is either the top level root of the + /// alias tree, or that you only want to work with the subtree rooted + /// at this specific symbol, and + /// (3) You think that all aliases in the subtree should always have the + /// operation applied. + SubTree, + + /// Apply the operation to all aliases in the alias tree containing the given + /// symbol (i.e. the whole alias tree as seen from the top-level alias root of + /// the given symbol, including sibling aliases). + /// + /// You should generally use the 'WholeTree' policy where all of the following + /// conditions hold: + /// (1) You're applying the operation to one specific Symbol (e.g. one + /// identified by name), rather than all symbols that satisfy a + /// generic predicate (e.g. "is in section X"), + /// (2) You believe that all symbols in the alias tree should have the + /// operation applied. + WholeTree, + + /// Do not apply the operation to any aliases (except the specified symbol + /// itself). + /// + /// You should generally use the 'None' policy where any of the following + /// conditions hold: + /// (1) You're applying the operation to all symbols that satisfy a generic + /// predicate, (in which case you'll be implicitly applying it to any + /// aliases in the loop that applies the operation). + /// (2) You don't think that the operation can be applied uniformly across + /// the aliases. + None = 0, + + /// Assert that the symbol has no aliases. Removes checks for aliases. + /// The caller is responsible for guaranteeing that the Symbol does not have + /// any aliases in the graph. + AssertNoAliases +}; + +/// Describes how to update aliases when a symbol is moved or removed. +enum class AliasMovePolicy { + /// Aliases of the given symbol become non-aliases. + /// + /// This policy should be used when the operation is being carried out on all + /// symbols in a section. + AliasesBecomeReal, + + /// The subtree rooted at the given tree is moved/removed, but the rest of + /// the alias tree (if any) is untouched. + /// + /// This policy should be used any time that the operation is being carried + /// out a specific named symbol, but should not affect the aliased symbol + /// or sibling aliases (if any). + SubTree, + + /// The whole alias tree containing the given symbol is moved. + /// + /// This policy should be used any time that the operation is being carried + /// out on a specific named symbol and should apply to the whole aliase tree + /// that the symbol belongs to. + WholeTree +}; + /// Symbol representation. /// /// Symbols represent locations within Addressable objects. @@ -411,6 +484,7 @@ setScope(S); setLive(IsLive); setCallable(IsCallable); + HasAliasInfo = false; } static Symbol &constructCommon(BumpPtrAllocator &Allocator, Block &Base, @@ -450,8 +524,8 @@ static Symbol &constructAnonDef(BumpPtrAllocator &Allocator, Block &Base, orc::ExecutorAddrDiff Offset, - orc::ExecutorAddrDiff Size, bool IsCallable, - bool IsLive) { + orc::ExecutorAddrDiff Size, bool IsLive, + bool IsCallable) { assert((Offset + Size) <= Base.getSize() && "Symbol extends past end of block"); auto *Sym = Allocator.Allocate(); @@ -472,6 +546,18 @@ return *Sym; } + static Symbol &constructAlias(BumpPtrAllocator &Allocator, Symbol &Target, + StringRef Name, orc::ExecutorAddrDiff Size, + Linkage L, Scope S, bool IsLive, + bool IsCallable) { + assert(!Name.empty() && "Name cannot be empty"); + auto *Sym = Allocator.Allocate(); + new (Sym) Symbol(Target.getAddressable(), Target.getOffset(), Name, Size, L, + S, IsLive, IsCallable); + Sym->HasAliasInfo = true; + return *Sym; + } + public: /// Create a null Symbol. This allows Symbols to be default initialized for /// use in containers (e.g. as map values). Null symbols are only useful for @@ -590,7 +676,7 @@ /// Returns the content in the underlying block covered by this symbol. /// This method may only be called on defined non-zero-fill symbols. ArrayRef getSymbolContent() const { - return getBlock().getContent().slice(Offset, Size); + return getBlock().getContent().slice(Offset, getSize()); } /// Get the linkage for this Symbol. @@ -640,17 +726,18 @@ Offset = NewOffset; } - static constexpr uint64_t MaxOffset = (1ULL << 59) - 1; + static constexpr uint64_t MaxOffset = (1ULL << 58) - 1; // FIXME: A char* or SymbolStringPtr may pack better. StringRef Name; Addressable *Base = nullptr; - uint64_t Offset : 59; + uint64_t Offset : 58; uint64_t L : 1; uint64_t S : 2; uint64_t IsLive : 1; uint64_t IsCallable : 1; - size_t Size = 0; + uint64_t HasAliasInfo : 1; + uint64_t Size; }; raw_ostream &operator<<(raw_ostream &OS, const Symbol &A); @@ -819,6 +906,17 @@ using ExternalSymbolSet = DenseSet; using BlockSet = DenseSet; + /// Struct containing info for symbols that alias other symbols, or are + /// aliased by other symbols. + struct AliasInfo { + using AliasList = SmallVector; + + Symbol *Target = nullptr; // Target (aliased) symbol. Null if root. + AliasList Aliases; // Aliases of symbol, if any. + }; + + using AliasInfoMap = DenseMap; + template Addressable &createAddressable(ArgTs &&... Args) { Addressable *A = @@ -940,6 +1038,79 @@ Section::const_block_iterator, const Block *, getSectionConstBlocks>; + /// An iterator over the immediate aliases of a symbol. + using alias_iterator = AliasInfo::AliasList::const_iterator; + + /// A DFS iterator over the alias-tree rooted at this symbol. + class alias_tree_iterator { + friend class LinkGraph; + + private: + struct WorkingItem { + AliasInfo *AI = nullptr; + size_t Idx = 0; + Symbol *getCurrent() const { return AI->Aliases[Idx]; } + bool atEnd() const { return Idx == AI->Aliases.size(); } + bool operator==(const WorkingItem &Other) const { + return AI == Other.AI && Idx == Other.Idx; + } + bool operator!=(const WorkingItem &Other) const { + return !(*this == Other); + } + }; + + public: + alias_tree_iterator() = default; + + Symbol *operator*() const { return WS.back().getCurrent(); } + + alias_tree_iterator &operator++() { + assert(G && "Cannot increment default iterator"); + assert(!WS.empty() && "Cannot increment end"); + + // Get a pointer to the current symbol before we advance. + auto *S = WS.back().getCurrent(); + ++WS.back().Idx; // Advance to the next symbol in this level. + + auto *AI = G->getAliasInfo(*S); + if (AI && !AI->Aliases.empty()) { + // If the current symbol has any children then we want to + // visit them before we visit the next symbol in this level, + // so add them to the working stack. + WS.push_back({AI, 0}); + } else { + // Otherwise, check whether we're at the end of the current level and, + // if we are, pop this and any other levels that are at the end. + while (!WS.empty() && WS.back().atEnd()) + WS.pop_back(); + } + return *this; + } + + bool operator==(const alias_tree_iterator &Other) const { + return WS == Other.WS; + } + bool operator!=(const alias_tree_iterator &Other) const { + return WS != Other.WS; + } + + private: + alias_tree_iterator(LinkGraph &G, Symbol &Root, bool IncludeRoot) : G(&G) { + if (IncludeRoot) { + PseudoAI.Aliases.push_back(&Root); + WS.push_back({&PseudoAI, 0}); + } else { + auto *AI = this->G->getAliasInfo(Root); + if (AI && !AI->Aliases.empty()) + WS.push_back({AI, 0}); + } + } + + LinkGraph *G = nullptr; + AliasInfo PseudoAI; // Used when including root in tree. + SmallVector WS; // Workstack. + }; + using GetEdgeKindNameFunction = const char *(*)(Edge::Kind); LinkGraph(std::string Name, const Triple &TT, unsigned PointerSize, @@ -1130,7 +1301,7 @@ orc::ExecutorAddrDiff Size, bool IsCallable, bool IsLive) { auto &Sym = Symbol::constructAnonDef(Allocator, Content, Offset, Size, - IsCallable, IsLive); + IsLive, IsCallable); Content.getSection().addSymbol(Sym); return Sym; } @@ -1150,6 +1321,38 @@ return Sym; } + /// Add a symbol alias. + /// + /// The Target symbol can be any external, absolute, or defined symbol. + /// + /// The alias will initially take on the scope, liveness, and callable-ness of + /// the Target. + Symbol &addAliasSymbol(Symbol &Target, StringRef Name, + orc::ExecutorAddrDiff Size, Linkage L) { + auto &Sym = Symbol::constructAlias(Allocator, Target, Name, Size, L, + Target.getScope(), Target.isLive(), + Target.isCallable()); + // Update alias info map. + assert(!AliasInfos.count(&Sym) && "AliasInfos map has entry already"); + auto &AI = AliasInfos[&Sym]; + AI.Target = &Target; + + Target.HasAliasInfo = true; + auto &TAI = AliasInfos[&Target]; + TAI.Aliases.push_back(&Sym); + + // Add the sym to the appropriate list. + if (Target.isDefined()) + Target.getBlock().getSection().addSymbol(Sym); + else if (Target.isExternal()) + ExternalSymbols.insert(&Sym); + else if (Target.isAbsolute()) + AbsoluteSymbols.insert(&Sym); + else + llvm_unreachable("Unrecognized symbol type"); + return Sym; + } + iterator_range sections() { return make_range(section_iterator(Sections.begin()), section_iterator(Sections.end())); @@ -1195,110 +1398,169 @@ const_defined_symbol_iterator(Sections.end(), Sections.end())); } + /// If the given symbol is an alias then this method returns the symbol that + /// it aliases. If the given symbol is not an alias then this method returns + /// null. + Symbol *getAliasTarget(Symbol &S) const { + if (LLVM_LIKELY(!S.HasAliasInfo)) + return nullptr; + return getAliasInfo(S)->Target; + } + + /// Returns true if the given symbol is an alias for another. + bool isAlias(Symbol &S) const { return getAliasTarget(S) != nullptr; } + + /// Returns the "real" symbol (the top-level root of the alias tree) pointed + /// to by the given symbol. If this symbol is a non-alias this method will + /// return the symbol itself. + Symbol &getAliasRoot(Symbol &S) { + if (LLVM_LIKELY(!S.HasAliasInfo)) + return S; + Symbol *Root = &S; + while (auto *Next = getAliasTarget(*Root)) + Root = Next; + return *Root; + } + + /// Returns true if the given symbol has no aliases. + bool aliases_empty(Symbol &S) const { + if (LLVM_LIKELY(!S.HasAliasInfo)) + return true; + return getAliasInfo(S)->Aliases.empty(); + } + + /// Returns the number of aliases of the given symbol. + size_t aliases_size(Symbol &S) const { + if (LLVM_LIKELY(!S.HasAliasInfo)) + return 0; + return getAliasInfo(S)->Aliases.size(); + } + + /// Returns an iterator to the start of the list of immediate aliases for the + /// given symbol. This does *not* include transitive aliases. E.g. For + /// A -> B -> C, the list of aliases of C is [B] only. + alias_iterator aliases_begin(Symbol &S) const { + if (LLVM_LIKELY(S.HasAliasInfo)) + return getAliasInfo(S)->Aliases.begin(); + return alias_iterator(); + } + + /// Returns an iterator to the end of the list of immediate aliases for the + /// given symbol. + alias_iterator aliases_end(Symbol &S) const { + if (LLVM_LIKELY(S.HasAliasInfo)) + return getAliasInfo(S)->Aliases.end(); + return alias_iterator(); + } + + /// Returns an iterator range for the list of all immediate aliases for the + /// given symbol. + iterator_range aliases(Symbol &S) const { + if (!LLVM_LIKELY(S.HasAliasInfo)) + return iterator_range(alias_iterator(), alias_iterator()); + auto &Aliases = getAliasInfo(S)->Aliases; + return iterator_range(Aliases.begin(), Aliases.end()); + } + + /// Returns an iterator to the start of the list of all aliases (including + /// transitive aliases) of the given symbol. + /// If IncludeSelf is true (the default) then this iterator will point to the + /// given symbol, otherwise it will point to the first alias of the given + /// symbol. + alias_tree_iterator alias_tree_begin(Symbol &S, bool IncludeSelf = true) { + if (!IncludeSelf && !S.HasAliasInfo) + return alias_tree_iterator(); + return alias_tree_iterator(*this, S, IncludeSelf); + } + + /// Returns an iterator to the end of the list of all aliases (including + /// transitive aliases) of the given symbol. + alias_tree_iterator alias_tree_end(Symbol &S) { + return alias_tree_iterator(); + } + + /// Returns an iterator range for the list of all aliases (including + /// transitive aliases) of the given symbol. + iterator_range alias_tree(Symbol &S, + bool IncludeSelf = true) { + return {alias_tree_begin(S, IncludeSelf), alias_tree_end(S)}; + } + + /// Apply the given operation to aliases of Sym according to the policy in + /// AOP. + template + void applyToAliases(AliasOperationPolicy AOP, Symbol &S, Op &&O) { + if (AOP == AliasOperationPolicy::None) { + O(S); + return; + } + if (AOP == AliasOperationPolicy::AssertNoAliases) { + assert(aliases_empty(S) && "AssertNoAliases, but symbol is aliased"); + O(S); + return; + } + auto &Root = (AOP == AliasOperationPolicy::SubTree) ? S : getAliasRoot(S); + for (auto *AS : alias_tree(Root)) + O(*AS); + } + + /// Turns an alias symbol into a regular (non-alias) symbol. All other + /// properties are left unmodified. + void makeReal(Symbol &Sym) { + if (Sym.HasAliasInfo) + makeRealImpl(Sym); + } + + /// Make all aliases of the given symbol real. + void makeAliasesReal(Symbol &Sym) { + if (Sym.HasAliasInfo) + makeAliasesRealImpl(Sym); + } + /// Make the given symbol external (must not already be external). /// /// Symbol size, linkage and callability will be left unchanged. Symbol scope /// will be set to Default, and offset will be reset to 0. - void makeExternal(Symbol &Sym) { - assert(!Sym.isExternal() && "Symbol is already external"); - if (Sym.isAbsolute()) { - assert(AbsoluteSymbols.count(&Sym) && - "Sym is not in the absolute symbols set"); - assert(Sym.getOffset() == 0 && "Absolute not at offset 0"); - AbsoluteSymbols.erase(&Sym); - auto &A = Sym.getAddressable(); - A.setAbsolute(false); - A.setAddress(orc::ExecutorAddr()); - } else { - assert(Sym.isDefined() && "Sym is not a defined symbol"); - Section &Sec = Sym.getBlock().getSection(); - Sec.removeSymbol(Sym); - Sym.makeExternal(createAddressable(orc::ExecutorAddr(), false)); - } - ExternalSymbols.insert(&Sym); - } + void makeExternal(Symbol &Sym, AliasMovePolicy AMP); - /// Make the given symbol an absolute with the given address (must not already - /// be absolute). + /// Make the given symbol an absolute with the given address. If the given + /// symbol is already absolute this just updates the address. /// /// The symbol's size, linkage, and callability, and liveness will be left /// unchanged, and its offset will be reset to 0. /// /// If the symbol was external then its scope will be set to local, otherwise /// it will be left unchanged. - void makeAbsolute(Symbol &Sym, orc::ExecutorAddr Address) { - assert(!Sym.isAbsolute() && "Symbol is already absolute"); - if (Sym.isExternal()) { - assert(ExternalSymbols.count(&Sym) && - "Sym is not in the absolute symbols set"); - assert(Sym.getOffset() == 0 && "External is not at offset 0"); - ExternalSymbols.erase(&Sym); - auto &A = Sym.getAddressable(); - A.setAbsolute(true); - A.setAddress(Address); - Sym.setScope(Scope::Local); - } else { - assert(Sym.isDefined() && "Sym is not a defined symbol"); - Section &Sec = Sym.getBlock().getSection(); - Sec.removeSymbol(Sym); - Sym.makeAbsolute(createAddressable(Address)); - } - AbsoluteSymbols.insert(&Sym); - } + void makeAbsolute(Symbol &Sym, orc::ExecutorAddr Address, + AliasMovePolicy AMP); /// Turn an absolute or external symbol into a defined one by attaching it to /// a block. Symbol must not already be defined. + /// + /// Any aliases will be moved into the given Block. If this symbol was an + /// alias itself then it will cease to be an alias and become the root of its + /// alias tree. + /// + /// The size of any aliases will be updated according to the policy in AOP, + /// which defaults to updating the SubTree. void makeDefined(Symbol &Sym, Block &Content, orc::ExecutorAddrDiff Offset, - orc::ExecutorAddrDiff Size, Linkage L, Scope S, - bool IsLive) { - assert(!Sym.isDefined() && "Sym is already a defined symbol"); - if (Sym.isAbsolute()) { - assert(AbsoluteSymbols.count(&Sym) && - "Symbol is not in the absolutes set"); - AbsoluteSymbols.erase(&Sym); - } else { - assert(ExternalSymbols.count(&Sym) && - "Symbol is not in the externals set"); - ExternalSymbols.erase(&Sym); - } - Addressable &OldBase = *Sym.Base; - Sym.setBlock(Content); - Sym.setOffset(Offset); - Sym.setSize(Size); - Sym.setLinkage(L); - Sym.setScope(S); - Sym.setLive(IsLive); - Content.getSection().addSymbol(Sym); - destroyAddressable(OldBase); - } + orc::ExecutorAddrDiff Size, Linkage L, Scope S, bool IsLive, + AliasMovePolicy AMP); /// Transfer a defined symbol from one block to another. /// /// The symbol's offset within DestBlock is set to NewOffset. /// - /// If ExplicitNewSize is given as None then the size of the symbol will be - /// checked and auto-truncated to at most the size of the remainder (from the - /// given offset) of the size of the new block. + /// If ExplicitNewSize is None then the size of the symbol any aliases will be + /// checked and auto-truncated to at most the size of the remainder of the + /// given block. If ExplicitNewSize is not None then the size of the symbol + /// and any aliases will be set to the given size. /// /// All other symbol attributes are unchanged. void transferDefinedSymbol(Symbol &Sym, Block &DestBlock, orc::ExecutorAddrDiff NewOffset, - Optional ExplicitNewSize) { - auto &OldSection = Sym.getBlock().getSection(); - Sym.setBlock(DestBlock); - Sym.setOffset(NewOffset); - if (ExplicitNewSize) - Sym.setSize(*ExplicitNewSize); - else { - auto RemainingBlockSize = DestBlock.getSize() - NewOffset; - if (Sym.getSize() > RemainingBlockSize) - Sym.setSize(RemainingBlockSize); - } - if (&DestBlock.getSection() != &OldSection) { - OldSection.removeSymbol(Sym); - DestBlock.getSection().addSymbol(Sym); - } - } + Optional ExplicitNewSize, + AliasMovePolicy AMP); /// Transfers the given Block and all Symbols pointing to it to the given /// Section. @@ -1339,41 +1601,38 @@ removeSection(SrcSection); } - /// Removes an external symbol. Also removes the underlying Addressable. - void removeExternalSymbol(Symbol &Sym) { - assert(!Sym.isDefined() && !Sym.isAbsolute() && - "Sym is not an external symbol"); - assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set"); - ExternalSymbols.erase(&Sym); - Addressable &Base = *Sym.Base; - assert(llvm::none_of(ExternalSymbols, - [&](Symbol *AS) { return AS->Base == &Base; }) && - "Base addressable still in use"); - destroySymbol(Sym); - destroyAddressable(Base); - } - - /// Remove an absolute symbol. Also removes the underlying Addressable. - void removeAbsoluteSymbol(Symbol &Sym) { - assert(!Sym.isDefined() && Sym.isAbsolute() && - "Sym is not an absolute symbol"); - assert(AbsoluteSymbols.count(&Sym) && - "Symbol is not in the absolute symbols set"); - AbsoluteSymbols.erase(&Sym); - Addressable &Base = *Sym.Base; - assert(llvm::none_of(ExternalSymbols, - [&](Symbol *AS) { return AS->Base == &Base; }) && - "Base addressable still in use"); - destroySymbol(Sym); - destroyAddressable(Base); - } + /// Removes an external symbol. + /// + /// If AMP is ... + /// * AliasesBecomeReal: any aliases of this external become real (non-alias) + /// symbols. + /// * SubTree, and Sym is not the root of the alias tree: all symbols in the + /// subtree are removed. + /// * WholeTree, or Sym is the root of the alias tree: all symbols within the + /// tree containing Sym are removed, as is the underlying Addressable (which + /// is no longer needed). + void removeExternalSymbol(Symbol &Sym, AliasMovePolicy AMP); + + /// Remove an absolute symbol. + /// + /// If AMP is ... + /// * AliasesBecomeReal: any aliases of this external become real (non-alias) + /// symbols. + /// * SubTree, and Sym is not the root of the alias tree: all symbols in the + /// subtree are removed. + /// * WholeTree, or Sym is the root of the alias tree: all symbols within the + /// tree containing Sym are removed, as is the underlying Addressable (which + /// is no longer needed). + void removeAbsoluteSymbol(Symbol &Sym, AliasMovePolicy AMP); /// Removes defined symbols. Does not remove the underlying block. - void removeDefinedSymbol(Symbol &Sym) { - assert(Sym.isDefined() && "Sym is not a defined symbol"); - Sym.getBlock().getSection().removeSymbol(Sym); - destroySymbol(Sym); - } + /// + /// If AMP is ... + /// * AliasesBecomeReal: any aliases of this external become real (non-alias) + /// symbols. + /// * SubTree: All transitive aliases of Sym are removed. + /// * WholeTree: All symbols within the alias tree containing Sym are removed. + void removeDefinedSymbol(Symbol &Sym, AliasMovePolicy AMP); /// Remove a block. The block reference is defunct after calling this /// function and should no longer be used. @@ -1408,6 +1667,39 @@ void dump(raw_ostream &OS); private: + const AliasInfo *getAliasInfo(const Symbol &S) const { + if (!S.HasAliasInfo) { + assert(!AliasInfos.count(&S) && + "!S.HasAliasInfo, but AliasInfos contains entry"); + return nullptr; + } + auto I = AliasInfos.find(&S); + assert(I != AliasInfos.end() && + "S.HasAliasInfo, but AliasInfos does not contain entry"); + return &I->second; + } + + AliasInfo *getAliasInfo(const Symbol &S) { + return const_cast( + static_cast(this)->getAliasInfo(S)); + } + + class AliasInfoCleanup { + public: + AliasInfoCleanup(LinkGraph &G); + ~AliasInfoCleanup(); + void record(Symbol &S); + void apply(); + + private: + LinkGraph &G; + SmallVector Keys; + }; + + // --- Slow paths --- + void makeRealImpl(Symbol &Sym); + void makeAliasesRealImpl(Symbol &Sym); + // Put the BumpPtrAllocator first so that we don't free any of the underlying // memory until the Symbol/Addressable destructors have been run. BumpPtrAllocator Allocator; @@ -1420,6 +1712,7 @@ SectionList Sections; ExternalSymbolSet ExternalSymbols; ExternalSymbolSet AbsoluteSymbols; + AliasInfoMap AliasInfos; orc::shared::AllocActions AAs; }; diff --git a/llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp b/llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp --- a/llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp +++ b/llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp @@ -361,7 +361,8 @@ auto *Target = DefinedSymbols[KeyValue.second]; auto *Alias = ExternalSymbols[KeyValue.first]; G->makeDefined(*Alias, Target->getBlock(), Target->getOffset(), - Target->getSize(), Linkage::Weak, Scope::Local, false); + Target->getSize(), Linkage::Weak, Scope::Local, false, + AliasMovePolicy::SubTree); } return Error::success(); } diff --git a/llvm/lib/ExecutionEngine/JITLink/DefineExternalSectionStartAndEndSymbols.h b/llvm/lib/ExecutionEngine/JITLink/DefineExternalSectionStartAndEndSymbols.h --- a/llvm/lib/ExecutionEngine/JITLink/DefineExternalSectionStartAndEndSymbols.h +++ b/llvm/lib/ExecutionEngine/JITLink/DefineExternalSectionStartAndEndSymbols.h @@ -52,17 +52,17 @@ auto &SR = getSectionRange(*D.Sec); if (D.IsStart) { if (SR.empty()) - G.makeAbsolute(*Sym, orc::ExecutorAddr()); + G.makeAbsolute(*Sym, orc::ExecutorAddr(), AliasMovePolicy::SubTree); else G.makeDefined(*Sym, *SR.getFirstBlock(), 0, 0, Linkage::Strong, - Scope::Local, false); + Scope::Local, false, AliasMovePolicy::SubTree); } else { if (SR.empty()) - G.makeAbsolute(*Sym, orc::ExecutorAddr()); + G.makeAbsolute(*Sym, orc::ExecutorAddr(), AliasMovePolicy::SubTree); else G.makeDefined(*Sym, *SR.getLastBlock(), SR.getLastBlock()->getSize(), 0, Linkage::Strong, - Scope::Local, false); + Scope::Local, false, AliasMovePolicy::SubTree); } } } diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp b/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp --- a/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp +++ b/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp @@ -227,6 +227,248 @@ return NewBlock; } +void LinkGraph::makeExternal(Symbol &Sym, AliasMovePolicy AMP) { + // If the symbol is already external then just return. + if (Sym.isExternal()) + return; + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::SubTree ? Sym : getAliasRoot(Sym); + + if (Root.isDefined()) { + // Remove symbols from the section, point all of them at a newly + // created addressable. + auto &Sec = Root.getBlock().getSection(); + auto &NewAddressable = createAddressable(orc::ExecutorAddr(), false); + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + assert(AS.isDefined() && "AS is not a defined symbol"); + Sec.removeSymbol(AS); + AS.makeExternal(NewAddressable); + AS.setScope(Scope::Default); + ExternalSymbols.insert(&AS); + }); + } else { + // makeReal will create a new addressable for the tree. + makeReal(Root); + + // Update the underlying Addressable to make it external. + auto &A = Root.getAddressable(); + A.setAddress(orc::ExecutorAddr()); + A.setAbsolute(false); + + // Move all aliases in the tree from the AbsoluteSymbols to the + // ExternalSymbols list, and change all scopes to global. + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + assert(AS.isExternal() && "AS is not absolute"); + assert(AbsoluteSymbols.count(&AS) && + "AS is not in the absolute symbols set"); + assert(AS.getOffset() == 0 && "Absolute is not at offset 0"); + AS.makeExternal(A); + AS.setScope(Scope::Default); + AbsoluteSymbols.erase(&AS); + ExternalSymbols.insert(&AS); + }); + } +} + +void LinkGraph::makeAbsolute(Symbol &Sym, orc::ExecutorAddr Address, + AliasMovePolicy AMP) { + // Sym is already addressable. + if (Sym.isAbsolute()) { + Sym.getAddressable().setAddress(Address); + return; + } + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::SubTree ? Sym : getAliasRoot(Sym); + + if (Root.isDefined()) { + // Remove symbols from the section, point all of them at a newly + // created addressable. + auto &Sec = Root.getBlock().getSection(); + auto &NewAddressable = createAddressable(Address); + NewAddressable.setAbsolute(true); + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + assert(AS.isDefined() && "AS is not a defined symbol"); + Sec.removeSymbol(AS); + AS.makeAbsolute(NewAddressable); + AbsoluteSymbols.insert(&AS); + }); + } else { + // makeReal will create a new addressable for the tree. + makeReal(Root); + + // Update the underlying Addressable to point to the requested address. + auto &A = Root.getAddressable(); + A.setAddress(Address); + A.setAbsolute(true); + + // Move all aliases in the tree from the ExternalSymbols to the + // AbsoluteSymbols list, and change all scopes to local. + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + assert(AS.isAbsolute() && "AS is not absolute"); + assert(ExternalSymbols.count(&AS) && + "AS is not in the external symbols set"); + assert(AS.getOffset() == 0 && "External is not at offset 0"); + AS.makeAbsolute(A); + AS.setScope(Scope::Local); + ExternalSymbols.erase(&AS); + AbsoluteSymbols.insert(&AS); + }); + } +} + +void LinkGraph::makeDefined(Symbol &Sym, Block &Content, + orc::ExecutorAddrDiff Offset, + orc::ExecutorAddrDiff Size, Linkage L, Scope S, + bool IsLive, AliasMovePolicy AMP) { + assert(!Sym.isDefined() && "Sym is already a defined symbol"); + ExternalSymbolSet &CurSet = + Sym.isExternal() ? ExternalSymbols : AbsoluteSymbols; + assert(CurSet.count(&Sym) && "Symbol is not in the expected set"); + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::WholeTree ? getAliasRoot(Sym) : Sym; + + // If the root of the move is the root of the whole alias tree then we can + // destroy the old addressable, otherwise we need to keep it. + Addressable *OldBaseToRemove = nullptr; + if (!isAlias(Root)) + OldBaseToRemove = &Sym.getAddressable(); + + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + AS.setBlock(Content); + AS.setOffset(Offset); + AS.setSize(Size); + AS.setLinkage(L); + AS.setScope(S); + AS.setLive(IsLive); + Content.getSection().addSymbol(AS); + CurSet.erase(&AS); + }); + + if (OldBaseToRemove) + destroyAddressable(*OldBaseToRemove); +} + +void LinkGraph::transferDefinedSymbol( + Symbol &Sym, Block &DestBlock, orc::ExecutorAddrDiff NewOffset, + Optional ExplicitNewSize, AliasMovePolicy AMP) { + assert(Sym.isDefined() && "Sym is not defined"); + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::WholeTree ? getAliasRoot(Sym) : Sym; + + auto &OldSection = Sym.getBlock().getSection(); + auto &NewSection = DestBlock.getSection(); + + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + AS.setBlock(DestBlock); + AS.setOffset(NewOffset); + if (ExplicitNewSize) + AS.setSize(*ExplicitNewSize); + else { + auto RemainingBlockSize = DestBlock.getSize() - NewOffset; + if (AS.getSize() > RemainingBlockSize) + AS.setSize(RemainingBlockSize); + } + if (&NewSection != &OldSection) { + OldSection.removeSymbol(AS); + DestBlock.getSection().addSymbol(AS); + } + }); +} + +void LinkGraph::removeExternalSymbol(Symbol &Sym, AliasMovePolicy AMP) { + assert(!Sym.isDefined() && !Sym.isAbsolute() && + "Sym is not an external symbol"); + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::WholeTree ? getAliasRoot(Sym) : Sym; + + Addressable *BaseToRemove = nullptr; + if (!isAlias(Root)) + BaseToRemove = &Root.getAddressable(); + + // Destroy the symbols. + AliasInfoCleanup AIC(*this); + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + assert(ExternalSymbols.count(&AS) && "AS is not in the externals set"); + AIC.record(AS); + ExternalSymbols.erase(&AS); + destroySymbol(AS); + }); + AIC.apply(); + + // Destroy the base Addressable if no longer needed. + if (BaseToRemove) { + assert( + llvm::none_of(ExternalSymbols, + [&](Symbol *AS) { return AS->Base == BaseToRemove; }) && + "Base addressable still in use"); + destroyAddressable(*BaseToRemove); + } +} + +void LinkGraph::removeAbsoluteSymbol(Symbol &Sym, AliasMovePolicy AMP) { + assert(!Sym.isDefined() && Sym.isAbsolute() && + "Sym is not an absolute symbol"); + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::WholeTree ? getAliasRoot(Sym) : Sym; + + Addressable *BaseToRemove = nullptr; + if (!isAlias(Root)) + BaseToRemove = &Root.getAddressable(); + + AliasInfoCleanup AIC(*this); + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + assert(AbsoluteSymbols.count(&AS) && "AS is not in the absolutes set"); + AIC.record(AS); + AbsoluteSymbols.erase(&AS); + destroySymbol(AS); + }); + AIC.apply(); + + if (BaseToRemove) { + assert( + llvm::none_of(AbsoluteSymbols, + [&](Symbol *AS) { return AS->Base == BaseToRemove; }) && + "Base addressable still in use"); + destroyAddressable(*BaseToRemove); + } +} + +void LinkGraph::removeDefinedSymbol(Symbol &Sym, AliasMovePolicy AMP) { + assert(Sym.isDefined() && "Sym is not a defined symbol"); + + if (AMP == AliasMovePolicy::AliasesBecomeReal) + makeAliasesReal(Sym); + + auto &Root = AMP == AliasMovePolicy::WholeTree ? getAliasRoot(Sym) : Sym; + + auto &Sec = Root.getBlock().getSection(); + AliasInfoCleanup AIC(*this); + applyToAliases(AliasOperationPolicy::SubTree, Root, [&](Symbol &AS) { + AIC.record(AS); + Sec.removeSymbol(AS); + destroySymbol(AS); + }); + AIC.apply(); +} + void LinkGraph::dump(raw_ostream &OS) { DenseMap> BlockSymbols; @@ -323,6 +565,103 @@ OS << " none\n"; } +LinkGraph::AliasInfoCleanup::AliasInfoCleanup(LinkGraph &G) : G(G) {} + +LinkGraph::AliasInfoCleanup::~AliasInfoCleanup() { + assert(Keys.empty() && "AliasInfoCleanup::remove not called"); +} + +void LinkGraph::AliasInfoCleanup::record(Symbol &S) { + if (S.HasAliasInfo) + Keys.push_back(&S); +} + +void LinkGraph::AliasInfoCleanup::apply() { + for (auto *AS : Keys) { + assert(G.AliasInfos.count(AS) && "Missing AliasInfo"); + G.AliasInfos.erase(AS); + } +} + +void LinkGraph::makeRealImpl(Symbol &Sym) { + auto AII = AliasInfos.find(&Sym); + assert(AII != AliasInfos.end() && "Missing AliasInfos entry"); + + // If Sym is not an alias then just return. + auto &AI = AII->second; + if (!AI.Target) { + assert(AI.Aliases.empty() && "Unnecessary AliasInfo detected"); + return; + } + + // Remove this alias from the target's alias list. + auto TAII = AliasInfos.find(AI.Target); + assert(TAII != AliasInfos.end() && "Target has no AliasInfo"); + auto *TAI = &TAII->second; + assert(TAI && "Target AliasInfos entry is null"); + auto I = llvm::find(TAI->Aliases, &Sym); + assert(I != TAI->Aliases.end() && "Sym is not in target's alias list"); + TAI->Aliases.erase(I); + if (TAI->Aliases.empty()) { + // The symbol we aliased has no other aliases -- remove its AliasInfo. + AliasInfos.erase(TAII); + AI.Target->HasAliasInfo = false; + } + + // Reset our target to null. + AI.Target = nullptr; + + // If this Symbol is an external or absolute then we need to give it its + // own addressable. + if (Sym.isExternal()) { + auto &NewAddressable = createAddressable(orc::ExecutorAddr(), false); + for (auto *AS : alias_tree(Sym)) + AS->makeExternal(NewAddressable); + } else if (Sym.isAbsolute()) { + auto &NewAddressable = createAddressable(Sym.getAddress()); + for (auto *AS : alias_tree(Sym)) + AS->makeAbsolute(NewAddressable); + } + + // If Sym has no aliases itself then we can just destroy its alias info. + if (AI.Aliases.empty()) { + Sym.HasAliasInfo = false; + AliasInfos.erase(AII); + return; + } +} + +void LinkGraph::makeAliasesRealImpl(Symbol &Sym) { + auto AII = AliasInfos.find(&Sym); + assert(AII != AliasInfos.end() && "Missing AliasInfos entry"); + + // If Sym has no aliases then just return. + auto &AI = AII->second; + if (AI.Aliases.empty()) + return; + + // Otherwise make each alias real. + for (auto *AliasSym : AI.Aliases) { + auto AAII = AliasInfos.find(AliasSym); + assert(AAII != AliasInfos.end() && "Alias has no AliasInfo"); + auto &AAI = AAII->second; + // If the alias has no aliases of its own then destroy its alias info, + // otherwise just reset its target. + if (!AAI.Aliases.empty()) + AAI.Target = nullptr; + else { + AliasSym->HasAliasInfo = false; + AliasInfos.erase(AAII); + } + } + + AI.Aliases.clear(); + if (AI.Target == nullptr) { + AliasInfos.erase(AII); + Sym.HasAliasInfo = false; + } +} + raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF) { switch (LF) { case SymbolLookupFlags::RequiredSymbol: diff --git a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp --- a/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp +++ b/llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp @@ -285,7 +285,7 @@ SymbolsToRemove.push_back(Sym); for (auto *Sym : SymbolsToRemove) { LLVM_DEBUG(dbgs() << " " << *Sym << "...\n"); - G.removeDefinedSymbol(*Sym); + G.removeDefinedSymbol(*Sym, AliasMovePolicy::AliasesBecomeReal); } } @@ -311,7 +311,20 @@ SymbolsToRemove.push_back(Sym); for (auto *Sym : SymbolsToRemove) { LLVM_DEBUG(dbgs() << " " << *Sym << "...\n"); - G.removeExternalSymbol(*Sym); + G.removeExternalSymbol(*Sym, AliasMovePolicy::AliasesBecomeReal); + } + } + + // Collect any absolute symbols to remove, then remove them. + { + LLVM_DEBUG(dbgs() << "Removing unused absolute symbols:\n"); + std::vector SymbolsToRemove; + for (auto *Sym : G.absolute_symbols()) + if (!Sym->isLive()) + SymbolsToRemove.push_back(Sym); + for (auto *Sym : SymbolsToRemove) { + LLVM_DEBUG(dbgs() << " " << *Sym << "...\n"); + G.removeAbsoluteSymbol(*Sym, AliasMovePolicy::AliasesBecomeReal); } } } diff --git a/llvm/lib/ExecutionEngine/Orc/MachOPlatform.cpp b/llvm/lib/ExecutionEngine/Orc/MachOPlatform.cpp --- a/llvm/lib/ExecutionEngine/Orc/MachOPlatform.cpp +++ b/llvm/lib/ExecutionEngine/Orc/MachOPlatform.cpp @@ -795,7 +795,7 @@ // __objc_imageinfo is valid. Delete the block. for (auto *S : ObjCImageInfo->symbols()) - G.removeDefinedSymbol(*S); + G.removeDefinedSymbol(*S, jitlink::AliasMovePolicy::AliasesBecomeReal); G.removeBlock(ObjCImageInfoBlock); } else { // We haven't registered an __objc_imageinfo section yet. Register and diff --git a/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp b/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp --- a/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp +++ b/llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp @@ -104,7 +104,7 @@ if (Sym->getName() == *Name) { assert(Sym->getLinkage() == Linkage::Weak && "Discarding non-weak definition"); - G->makeExternal(*Sym); + G->makeExternal(*Sym, AliasMovePolicy::SubTree); break; } } @@ -449,7 +449,7 @@ for (auto &KV : NameToSym) if (!MR->getSymbols().count(KV.first)) - G.makeExternal(*KV.second); + G.makeExternal(*KV.second, AliasMovePolicy::AliasesBecomeReal); return Error::success(); } @@ -459,6 +459,9 @@ for (auto *Sym : G.defined_symbols()) if (Sym->hasName() && MR->getSymbols().count(ES.intern(Sym->getName()))) Sym->setLive(true); + for (auto *Sym : G.absolute_symbols()) + if (Sym->hasName() && MR->getSymbols().count(ES.intern(Sym->getName()))) + Sym->setLive(true); return Error::success(); } diff --git a/llvm/tools/llvm-jitlink/llvm-jitlink.cpp b/llvm/tools/llvm-jitlink/llvm-jitlink.cpp --- a/llvm/tools/llvm-jitlink/llvm-jitlink.cpp +++ b/llvm/tools/llvm-jitlink/llvm-jitlink.cpp @@ -374,7 +374,7 @@ } for (auto *Sym : DefinitionsToRemove) - G.makeExternal(*Sym); + G.makeExternal(*Sym, AliasMovePolicy::AliasesBecomeReal); return Error::success(); } diff --git a/llvm/unittests/ExecutionEngine/JITLink/EHFrameSupportTests.cpp b/llvm/unittests/ExecutionEngine/JITLink/EHFrameSupportTests.cpp --- a/llvm/unittests/ExecutionEngine/JITLink/EHFrameSupportTests.cpp +++ b/llvm/unittests/ExecutionEngine/JITLink/EHFrameSupportTests.cpp @@ -236,7 +236,7 @@ // Make '_a' external. for (auto *Sym : G->defined_symbols()) if (Sym->hasName() && Sym->getName() == "_a") { - G->makeExternal(*Sym); + G->makeExternal(*Sym, AliasMovePolicy::SubTree); break; } diff --git a/llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp b/llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp --- a/llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp +++ b/llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp @@ -249,8 +249,8 @@ // Make S1 and S2 external, confirm that the its flags are updated and that it // is moved from the defined/absolute symbols lists to the externals list. - G.makeExternal(S1); - G.makeExternal(S2); + G.makeExternal(S1, AliasMovePolicy::SubTree); + G.makeExternal(S2, AliasMovePolicy::SubTree); EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined"; EXPECT_TRUE(S1.isExternal()) << "Symbol should be external"; @@ -319,8 +319,8 @@ // is moved from the defined/external symbols lists to the absolutes list. orc::ExecutorAddr S1AbsAddr(0xA000); orc::ExecutorAddr S2AbsAddr(0xB000); - G.makeAbsolute(S1, S1AbsAddr); - G.makeAbsolute(S2, S2AbsAddr); + G.makeAbsolute(S1, S1AbsAddr, AliasMovePolicy::SubTree); + G.makeAbsolute(S2, S2AbsAddr, AliasMovePolicy::SubTree); EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined"; EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external"; @@ -374,7 +374,8 @@ // Make S1 defined, confirm that its flags are updated and that it is // moved from the defined symbols to the externals list. - G.makeDefined(S1, B1, 0, 4, Linkage::Strong, Scope::Default, false); + G.makeDefined(S1, B1, 0, 4, Linkage::Strong, Scope::Default, false, + AliasMovePolicy::SubTree); EXPECT_TRUE(S1.isDefined()) << "Symbol should be defined"; EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external"; @@ -411,14 +412,14 @@ Scope::Default, false, false); // Transfer with zero offset, explicit size. - G.transferDefinedSymbol(S1, B2, 0, 64); + G.transferDefinedSymbol(S1, B2, 0, 64, AliasMovePolicy::SubTree); EXPECT_EQ(&S1.getBlock(), &B2) << "Block was not updated"; EXPECT_EQ(S1.getOffset(), 0U) << "Unexpected offset"; EXPECT_EQ(S1.getSize(), 64U) << "Size was not updated"; // Transfer with non-zero offset, implicit truncation. - G.transferDefinedSymbol(S1, B3, 16, None); + G.transferDefinedSymbol(S1, B3, 16, None, AliasMovePolicy::SubTree); EXPECT_EQ(&S1.getBlock(), &B3) << "Block was not updated"; EXPECT_EQ(S1.getOffset(), 16U) << "Offset was not updated"; @@ -444,7 +445,7 @@ Scope::Default, false, false); // Transfer with zero offset, explicit size to section 2. - G.transferDefinedSymbol(S1, B2, 0, 64); + G.transferDefinedSymbol(S1, B2, 0, 64, AliasMovePolicy::SubTree); EXPECT_EQ(&S1.getBlock(), &B2) << "Block was not updated"; EXPECT_EQ(S1.getOffset(), 0U) << "Unexpected offset"; @@ -682,3 +683,192 @@ EXPECT_EQ(E2->getOffset(), 4U); } } + +static bool symNameLessThan(const Symbol *LHS, const Symbol *RHS) { + return LHS->getName() < RHS->getName(); +} + +TEST(LinkGraphTest, AliasBasic) { + // Check basic properties of aliases using a real symbol, A, plus two + // aliases: B -> A, and C -> B. + LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little, + getGenericEdgeKindName); + auto &Sec = G.createSection("__data", MemProt::Read | MemProt::Write); + auto &BL = + G.createContentBlock(Sec, BlockContent, orc::ExecutorAddr(0x1000), 8, 0); + auto &A = G.addDefinedSymbol(BL, 0, "A", 4, Linkage::Strong, Scope::Default, + false, false); + auto &B = G.addAliasSymbol(A, "B", 4, Linkage::Strong); + auto &C = G.addAliasSymbol(B, "C", 4, Linkage::Strong); + + auto &E = G.addExternalSymbol("E", 4, Linkage::Strong); + auto &F = G.addAliasSymbol(E, "F", 4, Linkage::Strong); + + auto &H = G.addAbsoluteSymbol("H", orc::ExecutorAddr(0x0001), 4, + Linkage::Strong, Scope::Default, false); + auto &I = G.addAliasSymbol(H, "I", 4, Linkage::Strong); + + // Check isAlias / isAliased: + // * A is aliased but not an alias. + // * B is both aliased and an alias. + // * C is an alias, but not aliased. + EXPECT_FALSE(G.isAlias(A)); + EXPECT_TRUE(!G.aliases_empty(A)); + EXPECT_TRUE(G.isAlias(B)); + EXPECT_TRUE(!G.aliases_empty(B)); + EXPECT_TRUE(G.isAlias(C)); + EXPECT_TRUE(G.aliases_empty(C)); + + // Check getAliasTarget and getAliasRoot(). + EXPECT_EQ(&G.getAliasRoot(A), &A); + + EXPECT_EQ(G.getAliasTarget(B), &A); + EXPECT_EQ(&G.getAliasRoot(B), &A); + + EXPECT_EQ(G.getAliasTarget(C), &B); + EXPECT_EQ(&G.getAliasRoot(C), &A); + + // Property checks: + EXPECT_EQ(A.getAddress(), B.getAddress()); + EXPECT_EQ(B.getAddress(), C.getAddress()); + EXPECT_EQ(&A.getBlock(), &B.getBlock()); + EXPECT_EQ(&B.getBlock(), &C.getBlock()); + + EXPECT_EQ(E.getAddress(), F.getAddress()); + + EXPECT_EQ(H.getAddress(), I.getAddress()); + + // Expect aliases to appear when iterating symbol ranges: + // ... in sections: + SmallVector DataSyms; + llvm::copy(Sec.symbols(), std::back_inserter(DataSyms)); + llvm::sort(DataSyms, symNameLessThan); + EXPECT_EQ(ArrayRef(DataSyms), ArrayRef({&A, &B, &C})); + + // ... in the externals: + SmallVector ExtSyms; + llvm::copy(G.external_symbols(), std::back_inserter(ExtSyms)); + llvm::sort(ExtSyms, symNameLessThan); + EXPECT_EQ(ArrayRef(ExtSyms), ArrayRef({&E, &F})); + + // ... in the absolutes: + SmallVector AbsSyms; + llvm::copy(G.absolute_symbols(), std::back_inserter(AbsSyms)); + llvm::sort(AbsSyms, symNameLessThan); + EXPECT_EQ(ArrayRef(AbsSyms), ArrayRef({&H, &I})); +} + +TEST(LinkGraphTest, ImmediateAliasIteration) { + // Check iteration over immediate aliases. + // B, C, and D are all aliases of A. E is not aliased. + LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little, + getGenericEdgeKindName); + auto &Sec = G.createSection("__data", MemProt::Read | MemProt::Write); + auto &BL = + G.createContentBlock(Sec, BlockContent, orc::ExecutorAddr(0x1000), 8, 0); + auto &A = G.addDefinedSymbol(BL, 0, "A", 4, Linkage::Strong, Scope::Default, + false, false); + auto &B = G.addAliasSymbol(A, "B", 4, Linkage::Strong); + auto &C = G.addAliasSymbol(A, "C", 4, Linkage::Strong); + auto &D = G.addAliasSymbol(A, "D", 4, Linkage::Strong); + auto &E = G.addDefinedSymbol(BL, 0, "E", 4, Linkage::Strong, Scope::Default, + false, false); + + // Check that operations behave as expected for non-alias, non-aliased + // symbols. + EXPECT_TRUE(G.aliases_empty(E)); + EXPECT_EQ(G.aliases_size(E), 0U); + EXPECT_EQ(G.aliases_begin(E), G.aliases_end(E)); + + // Check that operations behave as expected for aliases that are not + // themselves aliased. + EXPECT_TRUE(G.aliases_empty(C)); + EXPECT_EQ(G.aliases_size(C), 0U); + EXPECT_EQ(G.aliases_begin(C), G.aliases_end(C)); + + // Check that operations behave as expected for aliased symbols. + EXPECT_FALSE(G.aliases_empty(A)); + EXPECT_EQ(G.aliases_size(A), 3U); + EXPECT_NE(G.aliases_begin(A), G.aliases_end(A)); + + SmallVector Syms; + llvm::copy(G.aliases(A), std::back_inserter(Syms)); + llvm::sort(Syms, symNameLessThan); + EXPECT_EQ(Syms[0], &B); + EXPECT_EQ(Syms[1], &C); + EXPECT_EQ(Syms[2], &D); +} + +TEST(LinkGraphTest, AliasTreeIteration) { + // Check iteration over alias trees (all transitive aliases of a root). + // Test tree(s) are: + // D -- B -- A + // E --/ / + // F -> C -/ + // H + + LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little, + getGenericEdgeKindName); + auto &Sec = G.createSection("__data", MemProt::Read | MemProt::Write); + auto &BL = + G.createContentBlock(Sec, BlockContent, orc::ExecutorAddr(0x1000), 8, 0); + auto &A = G.addDefinedSymbol(BL, 0, "A", 4, Linkage::Strong, Scope::Default, + false, false); + auto &B = G.addAliasSymbol(A, "B", 4, Linkage::Strong); + auto &C = G.addAliasSymbol(A, "C", 4, Linkage::Strong); + auto &D = G.addAliasSymbol(B, "D", 4, Linkage::Strong); + auto &E = G.addAliasSymbol(B, "D", 4, Linkage::Strong); + auto &F = G.addAliasSymbol(C, "F", 4, Linkage::Strong); + auto &H = G.addDefinedSymbol(BL, 0, "H", 4, Linkage::Strong, Scope::Default, + false, false); + + // For non-alias, non-aliased symbols: + // * When excluding self, we expect the alias tree to be empty. + // * When including self, we expect the alias tree to contain one node which + // dereferences to self. + EXPECT_EQ(G.alias_tree_begin(H, false), G.alias_tree_end(H)); + auto HATBegin = G.alias_tree_begin(H, true); + EXPECT_EQ(*HATBegin, &H); + EXPECT_EQ(++HATBegin, G.alias_tree_end(H)); + + // For a regular (non-alias) symbol that is aliased: + // ... including the root: + SmallVector AAliasesIncludingRoot; + llvm::copy(G.alias_tree(A, true), std::back_inserter(AAliasesIncludingRoot)); + llvm::sort(AAliasesIncludingRoot, symNameLessThan); + EXPECT_EQ(ArrayRef(AAliasesIncludingRoot), + ArrayRef({&A, &B, &C, &D, &E, &F})); + // ... excluding the root: + SmallVector AAliasesExcludingRoot; + llvm::copy(G.alias_tree(A, false), std::back_inserter(AAliasesExcludingRoot)); + llvm::sort(AAliasesExcludingRoot, symNameLessThan); + EXPECT_EQ(ArrayRef(AAliasesExcludingRoot), + ArrayRef({&B, &C, &D, &E, &F})); + + // For an alias which is also aliased: + // ... including the root: + SmallVector BAliasesIncludingRoot; + llvm::copy(G.alias_tree(B, true), std::back_inserter(BAliasesIncludingRoot)); + llvm::sort(BAliasesIncludingRoot, symNameLessThan); + EXPECT_EQ(ArrayRef(BAliasesIncludingRoot), + ArrayRef({&B, &D, &E})); + // ... excluding the root: + SmallVector BAliasesExcludingRoot; + llvm::copy(G.alias_tree(B, false), std::back_inserter(BAliasesExcludingRoot)); + llvm::sort(BAliasesExcludingRoot, symNameLessThan); + EXPECT_EQ(ArrayRef(BAliasesExcludingRoot), + ArrayRef({&D, &E})); + + // For an alias that is not itself aliased: + // ... including the root: + SmallVector DAliasesIncludingRoot; + llvm::copy(G.alias_tree(D, true), std::back_inserter(DAliasesIncludingRoot)); + llvm::sort(DAliasesIncludingRoot, symNameLessThan); + EXPECT_EQ(ArrayRef(DAliasesIncludingRoot), + ArrayRef({&D})); + // ... excluding the root: + SmallVector DAliasesExcludingRoot; + llvm::copy(G.alias_tree(D, false), std::back_inserter(DAliasesExcludingRoot)); + llvm::sort(DAliasesExcludingRoot, symNameLessThan); + EXPECT_EQ(ArrayRef(DAliasesExcludingRoot), ArrayRef()); +}