[JITLink] Add support for symbol aliases.

[lhames]

Summary

MachO, ELF and COFF all include support for symbol aliases -- alternative names
for existing symbols. They tend to be rare (JITLink has survived without them
until now), but we need to be able to support them where they are used.

This commit introduces alias support to the LinkGraph by adding new operations
on the Symbol class (and associated helpers in the LinkGraph). By representing
aliases as Symbol objects we avoid introducing a new abstraction and maintain
the property that Edges point at Symbols.

Aliases can be added using the addAlias method. Aliases have a target Symbol
(the symbol that they alias), Name, Size, and Linkage. By default aliases take
their Scope, Liveness, and Callability from the target symbol, though these
properties can be modified independently after they're created.

New LinkGraph operations are introduced to support inspecting aliases:

• isAlias -- Returns true for symbols that are aliases, false otherwise.

• getAliasTarget -- If the given symbol is an alias then returns the symbol that it is an alias for, otherwise returns null.

• getAliasRoot -- Returns the "real" symbol that the given symbol points to, through any number of intermediate aliases (returns the given symbol itself if it is not an alias).

• aliases_empty, aliases_size, aliases_begin, aliases_end, aliases -- Standard container-like operations on the list of aliases for the given symbol.

• alias_tree_begin, alias_tree_end, alias_tree -- Provides iteration over the tree of aliases rooted at the given symbol. E.g. give the alias relationships [ A -> B, B -> C, D -> C ], alias_tree(C) will return the sequence [C, B, A, D]. Iteration with alias_tree is useful because it allows clients to write simple loops over all aliases (immediate and transitive) of a given symbol to update them.

• applyToAliases -- Iterates over all aliases of a given symbol according to an AliasOperationPolicy argument, which is SubTree (operate on all aliases in the tree rooted at the given symbol), WholeTree (operate on all aliases of the tree rooted at the alias root of the given symbol, i.e. *all* aliases including parents and siblings), None (do not apply the operation to any Symbols other than the given one), or AssertNoAlias (an optimized version of None that strips any checks for alias info). The applyToAliases method is used in the updated implementation of several existing LinkGraph methods.

In addition to the new operations, several existing operations have had an
AliasMovePolicy argument added, which controls how aliases of the given Symbol
are handled when moving the given Symbol within the LinkGraph, or removing it
from the LinkGraph. The AliasesBecomeReal policy will cause any aliases to
become "real", disconnecting them from the symbol being operated on and
allowing them to keep their existing properties and location. The SubTree
policy will cause the move/removal to apply to the alias tree rooted at the
given Symbol. The WholeTree policy will cause the move/removal to apply to all
aliases in the alias tree, including parents and siblings of the given Symbol.

Together these changes aim to satisify the following:

• Avoid substantially increasing costs for non-aliases. The new HasAliasInfo internal flag on Symbol allows us to quickly identify symbols that are neither aliases nor aliased (hopefully this will cover the majority of symbols) and skip any further alias-related work.

• Allow clients to treat aliases like ordinary symbols for most purposes. E.g. aliases will show up during symbol iteration like any ordinary symbol, keeping "find-by-name" searches simple.

• Allow clients to easily update groups of aliases (via alias_tree iteration).

• Provide detailed alias information to clients who want it (via aliases(...) and getAliasTarget(...))

• Force clients to think about aliases where they need to in order to keep them consistent. E.g. Requiring a policy choice when moving or removing symbols.

[lhames]

A couple of quick notes:

1. This still needs some more unit tests.

2. All the manual work to keep aliases consistently located is pretty gross. The main motivation for all this is that it would allow plugin writers to manipulate aliases separately. E.g. Even given "foo is an alias for bar", a plugin writer could choose to redirect those symbols to different places (e.g. to count entries via the "foo" and "bar" entrypoint differently). If we're willing to give that ability up we could potentially put all of the alias info (the names, sizes, linkages, scopes, etc.) into the AliasInfos side table and only keep the root Symbol in the graph, eliminating the consistency-maintenance work.

[lhames]

Another approach worth considering: What if we treated alias relationships like module-level metadata? I.e. JITLink wouldn't enforce the invariant that aliases point to the same location. Symbols would remain fully independent (as they are now), and we would just track the symbolic "<a> is an alias for <b>" relationship metadata on the side. Clients would be responsible for updating that if/where needed (although it would be automatically updated on symbol removal to avoid leaving stale entries).

The advantages: Simpler LinkGraph implementation. Clients can still access the metadata, and it provides an easy way to work with aliases where needed (the alias and alias-tree iterators would remain). Clients that don't want or need to care about aliases can ignore them.

The disadvantage: the "intent" of the metadata would be obscured by any passes that move alias symbols relative to one another without explicitly updating the metadata. E.g. if you have a graph containing symbol A and an alias B of A, and pass X decides to move B only to a different location, what should a later pass make of the relationship "B is an alias of A"?

That disadvantage is real, but seems likely to be rare. Given that JITLink pipelines and passes are also likely to remain relatively simple I think we could take this module-level-metadata route and then update passes to preserve metadata as needed.

[benlangmuir]

Does the SubTree v. WholeTree terminology have precedent anywhere? I personally didn't find it suggestive enough to guess what it would mean, I think because I mostly think about aliases of regular symbols not aliases of aliases (ie. the "tree" part). Just a suggestion: how about SubAliases and AllAliases. If you disagree, feel free to stick with the current names, I don't feel that strongly about it.

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

434

Is there a reason that AliasMovePolicy does not also have this option?

918

I'm worried about this type storing AliasInfo by value. You're holding references and returning pointers to the values in several places, which I worry is going to blow up if you accidentally insert into the map at the wrong time. I haven't found any actual UAF in the below code, but there are several footguns here -- AliasInfo &AI that is lexically in scope after a mutation of the map (ie. only working because nothing touches AI again) -- also you're relying on the fact DenseMap::erase never shrinks.

1459

Why is it "LLVM_LIKELY" that there are aliases? I would have expected the opposite here. Same for aliases_begin and aliases_end above.

[lhames]

@benlangmuir Any take on the alternative proposal -- make alias metadata available, but leave it to clients to act on?

In that case the alias infrastructure and iterators from this patch would remain, but we'd drop the MovePolicy and automated updates for aliases.

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

434

AssertNoAliases was introduced early. I think that by the end of the patch I'd decided that it was a bad idea, but forgot to take it back out.

918

You're right -- you can definitely imagine an iteration over aliases being used to insert new aliases.

Aliases are expected to be rare -- we can probably allocate entries in the graph's BumpPtrAllocator and hold pointers to them in the map.

1459

I think the logic was "If you were writing general-case code for symbols that _might_ be aliased then you would have used alias_tree, so a call to aliases suggests knowledge that a symbol is aliased".

I don't really think this needs to be optimized though -- I'll just remove it.

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

enum class Scope : uint8_t {
   Local
 };
 
 /// For debugging output.
 const char *getScopeName(Scope S);
 
 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.
 /// They can be either Named or Anonymous.
 /// Anonymous symbols have neither linkage nor visibility, and must point at
 /// ContentBlocks.
 /// Named symbols may be in one of four states:
 ///   - Null: Default initialized. Assignable, but otherwise unusable.
Symbol(Addressable &Base, orc::ExecutorAddrDiff Offset, StringRef Name,
          orc::ExecutorAddrDiff Size, Linkage L, Scope S, bool IsLive,
          bool IsCallable)
       : Name(Name), Base(&Base), Offset(Offset), Size(Size) {
     assert(Offset <= MaxOffset && "Offset out of range");
     setLinkage(L);
     setScope(S);
     setLive(IsLive);
     setCallable(IsCallable);
+    HasAliasInfo = false;
   }
 
   static Symbol &constructCommon(BumpPtrAllocator &Allocator, Block &Base,
                                  StringRef Name, orc::ExecutorAddrDiff Size,
                                  Scope S, bool IsLive) {
     assert(!Name.empty() && "Common symbol name cannot be empty");
     assert(Base.isDefined() &&
            "Cannot create common symbol from undefined block");
assert(!Base.isDefined() &&
            "Cannot create absolute symbol from a defined block");
     auto *Sym = Allocator.Allocate<Symbol>();
     new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
     return *Sym;
   }
 
   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<Symbol>();
     new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
                      Scope::Local, IsLive, IsCallable);
     return *Sym;
   }
 
   static Symbol &constructNamedDef(BumpPtrAllocator &Allocator, Block &Base,
                                    orc::ExecutorAddrDiff Offset, StringRef Name,
                                    orc::ExecutorAddrDiff Size, Linkage L,
                                    Scope S, bool IsLive, bool IsCallable) {
     assert((Offset + Size) <= Base.getSize() &&
            "Symbol extends past end of block");
     assert(!Name.empty() && "Name cannot be empty");
     auto *Sym = Allocator.Allocate<Symbol>();
     new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
     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<Symbol>();
+    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
   /// assigning to.
   Symbol() = default;
 
   // Symbols are not movable or copyable.
   Symbol(const Symbol &) = delete;
public:
 
   /// Returns true if this symbol is backed by a zero-fill block.
   /// This method may only be called on defined symbols.
   bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }
 
   /// Returns the content in the underlying block covered by this symbol.
   /// This method may only be called on defined non-zero-fill symbols.
   ArrayRef<char> getSymbolContent() const {
-    return getBlock().getContent().slice(Offset, Size);
+    return getBlock().getContent().slice(Offset, getSize());
   }
 
   /// Get the linkage for this Symbol.
   Linkage getLinkage() const { return static_cast<Linkage>(L); }
 
   /// Set the linkage for this Symbol.
   void setLinkage(Linkage L) {
     assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) &&
private:
 
   void setBlock(Block &B) { Base = &B; }
 
   void setOffset(orc::ExecutorAddrDiff NewOffset) {
     assert(NewOffset <= MaxOffset && "Offset out of range");
     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);
 
 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
                StringRef EdgeKindName);
 
 /// Represents an object file section.

 };
 
 class LinkGraph {
 private:
   using SectionList = std::vector<std::unique_ptr<Section>>;
   using ExternalSymbolSet = DenseSet<Symbol *>;
   using BlockSet = DenseSet<Block *>;
 
+  /// Struct containing info for symbols that alias other symbols, or are
+  /// aliased by other symbols.
+  struct AliasInfo {
+    using AliasList = SmallVector<Symbol *, 1>;
+
+    Symbol *Target = nullptr; // Target (aliased) symbol. Null if root.
+    AliasList Aliases;        // Aliases of symbol, if any.
+  };
+
+  using AliasInfoMap = DenseMap<const Symbol *, AliasInfo>;
+
   template <typename... ArgTs>
   Addressable &createAddressable(ArgTs &&... Args) {
     Addressable *A =
         reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
     new (A) Addressable(std::forward<ArgTs>(Args)...);
     return *A;
   }
 
using block_iterator = nested_collection_iterator<const_section_iterator,
                                                     Section::block_iterator,
                                                     Block *, getSectionBlocks>;
 
   using const_block_iterator =
       nested_collection_iterator<const_section_iterator,
                                  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<WorkingItem, 2> WS; // Workstack.
+  };
+
   using GetEdgeKindNameFunction = const char *(*)(Edge::Kind);
 
   LinkGraph(std::string Name, const Triple &TT, unsigned PointerSize,
             support::endianness Endianness,
             GetEdgeKindNameFunction GetEdgeKindName)
       : Name(std::move(Name)), TT(TT), PointerSize(PointerSize),
         Endianness(Endianness), GetEdgeKindName(std::move(GetEdgeKindName)) {}
 
Symbol &addCommonSymbol(StringRef Name, Scope S, Section &Section,
     return Sym;
   }
 
   /// Add an anonymous symbol.
   Symbol &addAnonymousSymbol(Block &Content, orc::ExecutorAddrDiff Offset,
                              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;
   }
 
   /// Add a named symbol.
   Symbol &addDefinedSymbol(Block &Content, orc::ExecutorAddrDiff Offset,
                            StringRef Name, orc::ExecutorAddrDiff Size,
                            Linkage L, Scope S, bool IsCallable, bool IsLive) {
     assert((S == Scope::Local || llvm::count_if(defined_symbols(),
                                                 [&](const Symbol *Sym) {
                                                   return Sym->getName() == Name;
                                                 }) == 0) &&
            "Duplicate defined symbol");
     auto &Sym = Symbol::constructNamedDef(Allocator, Content, Offset, Name,
                                           Size, L, S, IsLive, IsCallable);
     Content.getSection().addSymbol(Sym);
     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<section_iterator> sections() {
     return make_range(section_iterator(Sections.begin()),
                       section_iterator(Sections.end()));
   }
 
   SectionList::size_type sections_size() const { return Sections.size(); }
 
   /// Returns the section with the given name if it exists, otherwise returns
public:
   }
 
   iterator_range<const_defined_symbol_iterator> defined_symbols() const {
     return make_range(
         const_defined_symbol_iterator(Sections.begin(), Sections.end()),
         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<alias_iterator> aliases(Symbol &S) const {
+    if (!LLVM_LIKELY(S.HasAliasInfo))
+      return iterator_range<alias_iterator>(alias_iterator(), alias_iterator());
+    auto &Aliases = getAliasInfo(S)->Aliases;
+    return iterator_range<alias_iterator>(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_iterator> 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 <typename Op>
+  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<orc::ExecutorAddrDiff> 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<orc::ExecutorAddrDiff> ExplicitNewSize,
+                             AliasMovePolicy AMP);
 
   /// Transfers the given Block and all Symbols pointing to it to the given
   /// Section.
   ///
   /// No attempt is made to check compatibility of the source and destination
   /// sections. Blocks may be moved between sections with incompatible
   /// permissions (e.g. from data to text). The client is responsible for
   /// ensuring that this is safe.
if (&DstSection == &SrcSection)
       return;
     for (auto *B : SrcSection.blocks())
       B->setSection(DstSection);
     SrcSection.transferContentTo(DstSection);
     if (!PreserveSrcSection)
       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.
   void removeBlock(Block &B) {
     assert(llvm::none_of(B.getSection().symbols(),
                          [&](const Symbol *Sym) {
                            return &Sym->getBlock() == &B;
                          }) &&
public:
   /// Accessing this object after finalization will result in undefined
   /// behavior.
   orc::shared::AllocActions &allocActions() { return AAs; }
 
   /// Dump the graph.
   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<AliasInfo *>(
+        static_cast<const LinkGraph *>(this)->getAliasInfo(S));
+  }
+
+  class AliasInfoCleanup {
+  public:
+    AliasInfoCleanup(LinkGraph &G);
+    ~AliasInfoCleanup();
+    void record(Symbol &S);
+    void apply();
+
+  private:
+    LinkGraph &G;
+    SmallVector<Symbol *, 4> 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;
 
   std::string Name;
   Triple TT;
   unsigned PointerSize;
   support::endianness Endianness;
   GetEdgeKindNameFunction GetEdgeKindName = nullptr;
   SectionList Sections;
   ExternalSymbolSet ExternalSymbols;
   ExternalSymbolSet AbsoluteSymbols;
+  AliasInfoMap AliasInfos;
   orc::shared::AllocActions AAs;
 };
 
 inline MutableArrayRef<char> Block::getMutableContent(LinkGraph &G) {
   if (!ContentMutable)
     setMutableContent(G.allocateContent({Data, Size}));
   return MutableArrayRef<char>(const_cast<char *>(Data), Size);
 }

llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp

 
 Error COFFLinkGraphBuilder::handleAlternateNames() {
   for (auto &KeyValue : AlternateNames)
     if (DefinedSymbols.count(KeyValue.second) &&
         ExternalSymbols.count(KeyValue.first)) {
       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();
 }
 
 Symbol *COFFLinkGraphBuilder::createExternalSymbol(
     COFFSymbolIndex SymIndex, StringRef SymbolName,
     object::COFFSymbolRef Symbol, const object::coff_section *Section) {
   if (!ExternalSymbols.count(SymbolName))

llvm/lib/ExecutionEngine/JITLink/DefineExternalSectionStartAndEndSymbols.h

std::vector<Symbol *> Externals(G.external_symbols().begin(),
                                     G.external_symbols().end());
 
     for (auto *Sym : Externals) {
       SectionRangeSymbolDesc D = F(G, *Sym);
       if (D.Sec) {
         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);
         }
       }
     }
     return Error::success();
   }
 
 private:
   SectionRange &getSectionRange(Section &Sec) {

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

// Handle symbol transfer/update.
     // Update offsets for all remaining symbols in B.
     for (auto *Sym : BlockSymbols)
       Sym->setOffset(Sym->getOffset() - SplitIndex);
   }
 
   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<orc::ExecutorAddrDiff> 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<Block *, std::vector<Symbol *>> BlockSymbols;
 
   // Map from blocks to the symbols pointing at them.
   for (auto *Sym : defined_symbols())
     BlockSymbols[&Sym->getBlock()].push_back(Sym);
 
   // For each block, sort its symbols by something approximating
void LinkGraph::dump(raw_ostream &OS) {
   OS << "\nExternal symbols:\n";
   if (!llvm::empty(external_symbols())) {
     for (auto *Sym : external_symbols())
       OS << "  " << Sym->getAddress() << ": " << *Sym << "\n";
   } else
     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:
     return OS << "RequiredSymbol";
   case SymbolLookupFlags::WeaklyReferencedSymbol:
     return OS << "WeaklyReferencedSymbol";
   }
   llvm_unreachable("Unrecognized lookup flags");

llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp

void prune(LinkGraph &G) {
   {
     LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
     std::vector<Symbol *> SymbolsToRemove;
     for (auto *Sym : G.defined_symbols())
       if (!Sym->isLive())
         SymbolsToRemove.push_back(Sym);
     for (auto *Sym : SymbolsToRemove) {
       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
-      G.removeDefinedSymbol(*Sym);
+      G.removeDefinedSymbol(*Sym, AliasMovePolicy::AliasesBecomeReal);
     }
   }
 
   // Delete any unused blocks.
   {
     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
     std::vector<Block *> BlocksToRemove;
     for (auto *B : G.blocks())
void prune(LinkGraph &G) {
   {
     LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
     std::vector<Symbol *> SymbolsToRemove;
     for (auto *Sym : G.external_symbols())
       if (!Sym->isLive())
         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<Symbol *> 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);
     }
   }
 }
 
 } // end namespace jitlink
 } // end namespace llvm

llvm/lib/ExecutionEngine/Orc/MachOPlatform.cpp

if (ObjCImageInfoItr->second.first != Version)
           inconvertibleErrorCode());
     if (ObjCImageInfoItr->second.second != Flags)
       return make_error<StringError>("ObjC flags in " + G.getName() +
                                          " do not match first registered flags",
                                      inconvertibleErrorCode());
 
     // __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
     // move on. The section should already be marked no-dead-strip.
     ObjCImageInfos[&MR.getTargetJITDylib()] = std::make_pair(Version, Flags);
   }
 
   return Error::success();

llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp

LinkGraphMaterializationUnit(ObjectLinkingLayer &ObjLinkingLayer,
       : MaterializationUnit(std::move(LGI)), ObjLinkingLayer(ObjLinkingLayer),
         G(std::move(G)) {}
 
   void discard(const JITDylib &JD, const SymbolStringPtr &Name) override {
     for (auto *Sym : G->defined_symbols())
       if (Sym->getName() == *Name) {
         assert(Sym->getLinkage() == Linkage::Weak &&
                "Discarding non-weak definition");
-        G->makeExternal(*Sym);
+        G->makeExternal(*Sym, AliasMovePolicy::SubTree);
         break;
       }
   }
 
   ObjectLinkingLayer &ObjLinkingLayer;
   std::unique_ptr<LinkGraph> G;
   static std::atomic<uint64_t> Counter;
 };
Error claimOrExternalizeWeakAndCommonSymbols(LinkGraph &G) {
 
     // Attempt to claim all weak defs that we're not already responsible for.
     // This cannot fail -- any clashes will just result in rejection of our
     // claim, at which point we'll externalize that symbol.
     cantFail(MR->defineMaterializing(std::move(NewSymbolsToClaim)));
 
     for (auto &KV : NameToSym)
       if (!MR->getSymbols().count(KV.first))
-        G.makeExternal(*KV.second);
+        G.makeExternal(*KV.second, AliasMovePolicy::AliasesBecomeReal);
 
     return Error::success();
   }
 
   Error markResponsibilitySymbolsLive(LinkGraph &G) const {
     auto &ES = Layer.getExecutionSession();
     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();
   }
 
   Error computeNamedSymbolDependencies(LinkGraph &G) {
     auto &ES = MR->getTargetJITDylib().getExecutionSession();
     auto BlockDeps = computeBlockNonLocalDeps(G);
 
     // Compute dependencies for symbols defined in the JITLink graph.

llvm/tools/llvm-jitlink/llvm-jitlink.cpp

if (Sym->getLinkage() == Linkage::Weak) {
       continue;
     } else if (S.HarnessDefinitions.count(Sym->getName())) {
       LLVM_DEBUG(dbgs() << "  Externalizing " << Sym->getName() << "\n");
       DefinitionsToRemove.push_back(Sym);
     }
   }
 
   for (auto *Sym : DefinitionsToRemove)
-    G.makeExternal(*Sym);
+    G.makeExternal(*Sym, AliasMovePolicy::AliasesBecomeReal);
 
   return Error::success();
 }
 
 static uint64_t computeTotalBlockSizes(LinkGraph &G) {
   uint64_t TotalSize = 0;
   for (auto *B : G.blocks())
     TotalSize += B->getSize();

llvm/unittests/ExecutionEngine/JITLink/EHFrameSupportTests.cpp

 TEST(EHFrameCFIBlockInspector, ExternalPCBegin) {
   // Check that we don't crash if we transform the target of an FDE into an
   // external symbol before running edge-fixing.
   auto G = cantFail(createLinkGraphFromMachOObject_arm64(TestObject));
 
   // Make '_a' external.
   for (auto *Sym : G->defined_symbols())
     if (Sym->hasName() && Sym->getName() == "_a") {
-      G->makeExternal(*Sym);
+      G->makeExternal(*Sym, AliasMovePolicy::SubTree);
       break;
     }
 
   // Run the splitter and edge-fixer passes.
   cantFail(createEHFrameSplitterPass_MachO_arm64()(*G));
   cantFail(createEHFrameEdgeFixerPass_MachO_arm64()(*G));
 }

llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp

TEST(LinkGraphTest, MakeExternal) {
   EXPECT_TRUE(S2.isAbsolute()) << "Symbol should be absolute";
   EXPECT_EQ(
       std::distance(G.absolute_symbols().begin(), G.absolute_symbols().end()),
       1U)
       << "Unexpected number of symbols";
 
   // 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";
   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
   EXPECT_FALSE(S2.isDefined()) << "Symbol should not be defined";
   EXPECT_TRUE(S2.isExternal()) << "Symbol should be external";
   EXPECT_FALSE(S2.isAbsolute()) << "Symbol should not be absolute";
 
EXPECT_EQ(
       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
       1U)
       << "Unexpected number of symbols";
 
   // Make S1 and S2 absolute, confirm that the its flags are updated and that it
   // 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";
   EXPECT_TRUE(S1.isAbsolute()) << "Symbol should be absolute";
   EXPECT_FALSE(S2.isDefined()) << "Symbol should not be defined";
   EXPECT_FALSE(S2.isExternal()) << "Symbol should not be absolute";
   EXPECT_TRUE(S2.isAbsolute()) << "Symbol should be absolute";
 
EXPECT_EQ(
       << "Unexpected number of defined symbols";
   EXPECT_EQ(
       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
       1U)
       << "Unexpected number of external symbols";
 
   // 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";
   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
   EXPECT_TRUE(&S1.getBlock()) << "Symbol should have a non-null block";
   EXPECT_EQ(S1.getAddress(), orc::ExecutorAddr(0x1000U))
       << "Unexpected symbol address";
 
TEST(LinkGraphTest, TransferDefinedSymbol) {
   orc::ExecutorAddr B3Addr(0x3000);
   auto &B3 = G.createContentBlock(Sec, BlockContent.slice(0, 32), B3Addr, 8, 0);
 
   // Add a symbol.
   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong,
                                 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";
   EXPECT_EQ(S1.getSize(), 16U) << "Size was not updated";
 }
 
 TEST(LinkGraphTest, TransferDefinedSymbolAcrossSections) {
   // Check that we can transfer a defined symbol from an existing block in one
TEST(LinkGraphTest, TransferDefinedSymbolAcrossSections) {
   orc::ExecutorAddr B2Addr(0x2000);
   auto &B2 = G.createContentBlock(Sec2, BlockContent, B2Addr, 8, 0);
 
   // Add a symbol to section 1.
   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong,
                                 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";
   EXPECT_EQ(S1.getSize(), 64U) << "Size was not updated";
 
   EXPECT_EQ(Sec1.symbols_size(), 0u) << "Symbol was not removed from Sec1";
   EXPECT_EQ(Sec2.symbols_size(), 1u) << "Symbol was not added to Sec2";
   if (Sec2.symbols_size() == 1) {
if (size(B2.edges()) == 2) {
     auto *E1 = &*B2.edges().begin();
     auto *E2 = &*(B2.edges().begin() + 1);
     if (E2->getOffset() < E1->getOffset())
       std::swap(E1, E2);
     EXPECT_EQ(E1->getOffset(), 0U);
     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<Symbol *, 4> DataSyms;
+  llvm::copy(Sec.symbols(), std::back_inserter(DataSyms));
+  llvm::sort(DataSyms, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(DataSyms), ArrayRef<Symbol *>({&A, &B, &C}));
+
+  // ... in the externals:
+  SmallVector<Symbol *, 2> ExtSyms;
+  llvm::copy(G.external_symbols(), std::back_inserter(ExtSyms));
+  llvm::sort(ExtSyms, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(ExtSyms), ArrayRef<Symbol *>({&E, &F}));
+
+  // ... in the absolutes:
+  SmallVector<Symbol *, 2> AbsSyms;
+  llvm::copy(G.absolute_symbols(), std::back_inserter(AbsSyms));
+  llvm::sort(AbsSyms, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(AbsSyms), ArrayRef<Symbol *>({&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<Symbol *, 3> 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<Symbol *, 8> AAliasesIncludingRoot;
+  llvm::copy(G.alias_tree(A, true), std::back_inserter(AAliasesIncludingRoot));
+  llvm::sort(AAliasesIncludingRoot, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(AAliasesIncludingRoot),
+            ArrayRef<Symbol *>({&A, &B, &C, &D, &E, &F}));
+  // ... excluding the root:
+  SmallVector<Symbol *, 8> AAliasesExcludingRoot;
+  llvm::copy(G.alias_tree(A, false), std::back_inserter(AAliasesExcludingRoot));
+  llvm::sort(AAliasesExcludingRoot, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(AAliasesExcludingRoot),
+            ArrayRef<Symbol *>({&B, &C, &D, &E, &F}));
+
+  // For an alias which is also aliased:
+  // ... including the root:
+  SmallVector<Symbol *, 8> BAliasesIncludingRoot;
+  llvm::copy(G.alias_tree(B, true), std::back_inserter(BAliasesIncludingRoot));
+  llvm::sort(BAliasesIncludingRoot, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(BAliasesIncludingRoot),
+            ArrayRef<Symbol *>({&B, &D, &E}));
+  // ... excluding the root:
+  SmallVector<Symbol *, 8> BAliasesExcludingRoot;
+  llvm::copy(G.alias_tree(B, false), std::back_inserter(BAliasesExcludingRoot));
+  llvm::sort(BAliasesExcludingRoot, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(BAliasesExcludingRoot),
+            ArrayRef<Symbol *>({&D, &E}));
+
+  // For an alias that is not itself aliased:
+  // ... including the root:
+  SmallVector<Symbol *, 8> DAliasesIncludingRoot;
+  llvm::copy(G.alias_tree(D, true), std::back_inserter(DAliasesIncludingRoot));
+  llvm::sort(DAliasesIncludingRoot, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(DAliasesIncludingRoot),
+            ArrayRef<Symbol *>({&D}));
+  // ... excluding the root:
+  SmallVector<Symbol *, 8> DAliasesExcludingRoot;
+  llvm::copy(G.alias_tree(D, false), std::back_inserter(DAliasesExcludingRoot));
+  llvm::sort(DAliasesExcludingRoot, symNameLessThan);
+  EXPECT_EQ(ArrayRef<Symbol *>(DAliasesExcludingRoot), ArrayRef<Symbol *>());
+}