[JITLink] Switch from an atom-based model to a "blocks and symbols" model.

In the Atom model the symbols, content and relocations of a relocatable object
file are represented as a graph of atoms, where each Atom represents a
contiguous block of content with a single name (or no name at all if the
content is anonymous), and where edges between Atoms represent relocations.
If more than one symbol is associated with a contiguous block of content then
the content is broken into multiple atoms and layout constraints (represented by
edges) are introduced to ensure that the content remains effectively contiguous.
These layout constraints must be kept in mind when examining the content
associated with a symbol (it may be spread over multiple atoms) or when applying
certain relocation types (e.g. MachO subtractors).

This patch replaces the Atom model in JITLink with a blocks-and-symbols model.
The blocks-and-symbols model represents relocatable object files as bipartite
graphs, with one set of nodes representing contiguous content (Blocks) and
another representing named or anonymous locations (Symbols) within a Block.
Relocations are represented as edges from Blocks to Symbols. This scheme
removes layout constraints (simplifying handling of MachO alt-entry symbols,
and hopefully ELF sections at some point in the future) and simplifies some
relocation logic.

llvm-svn: 373689

3 files changed, 108 insertions, 103 deletions

diff --git a/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.cpp b/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.cpp
index 23f8a691c8f..c5d7dc2fdc9 100644
--- a/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.cpp
+++ b/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.cpp
@@ -145,7 +145,7 @@ void JITLinkTestCommon::TestJITLinkContext::notifyFailed(Error Err) {
 
 void JITLinkTestCommon::TestJITLinkContext::lookup(
     const DenseSet<StringRef> &Symbols,
-    JITLinkAsyncLookupContinuation LookupContinuation) {
+    std::unique_ptr<JITLinkAsyncLookupContinuation> LC) {
   jitlink::AsyncLookupResult LookupResult;
   DenseSet<StringRef> MissingSymbols;
   for (const auto &Symbol : Symbols) {
@@ -157,7 +157,7 @@ void JITLinkTestCommon::TestJITLinkContext::lookup(
   }
 
   if (MissingSymbols.empty())
-    LookupContinuation(std::move(LookupResult));
+    LC->run(std::move(LookupResult));
   else {
     std::string ErrMsg;
     {
@@ -167,12 +167,12 @@ void JITLinkTestCommon::TestJITLinkContext::lookup(
         ErrMsgStream << " " << Sym;
       ErrMsgStream << " ]\n";
     }
-    LookupContinuation(
+    LC->run(
         make_error<StringError>(std::move(ErrMsg), inconvertibleErrorCode()));
   }
 }
 
-void JITLinkTestCommon::TestJITLinkContext::notifyResolved(AtomGraph &G) {
+void JITLinkTestCommon::TestJITLinkContext::notifyResolved(LinkGraph &G) {
   if (NotifyResolved)
     NotifyResolved(G);
 }
@@ -186,7 +186,7 @@ void JITLinkTestCommon::TestJITLinkContext::notifyFinalized(
 Error JITLinkTestCommon::TestJITLinkContext::modifyPassConfig(
     const Triple &TT, PassConfiguration &Config) {
   if (TestCase)
-    Config.PostFixupPasses.push_back([&](AtomGraph &G) -> Error {
+    Config.PostFixupPasses.push_back([&](LinkGraph &G) -> Error {
       TestCase(G);
       return Error::success();
     });
@@ -196,11 +196,11 @@ Error JITLinkTestCommon::TestJITLinkContext::modifyPassConfig(
 JITLinkTestCommon::JITLinkTestCommon() { initializeLLVMTargets(); }
 
 Expected<std::pair<MCInst, size_t>>
-JITLinkTestCommon::disassemble(const MCDisassembler &Dis,
-                               jitlink::DefinedAtom &Atom, size_t Offset) {
+JITLinkTestCommon::disassemble(const MCDisassembler &Dis, jitlink::Block &B,
+                               size_t Offset) {
   ArrayRef<uint8_t> InstBuffer(
-      reinterpret_cast<const uint8_t *>(Atom.getContent().data()) + Offset,
-      Atom.getContent().size() - Offset);
+      reinterpret_cast<const uint8_t *>(B.getContent().data()) + Offset,
+      B.getContent().size() - Offset);
 
   MCInst Inst;
   uint64_t InstSize;
@@ -214,11 +214,9 @@ JITLinkTestCommon::disassemble(const MCDisassembler &Dis,
   return std::make_pair(Inst, InstSize);
 }
 
-Expected<int64_t>
-JITLinkTestCommon::decodeImmediateOperand(const MCDisassembler &Dis,
-                                          jitlink::DefinedAtom &Atom,
-                                          size_t OpIdx, size_t Offset) {
-  auto InstAndSize = disassemble(Dis, Atom, Offset);
+Expected<int64_t> JITLinkTestCommon::decodeImmediateOperand(
+    const MCDisassembler &Dis, jitlink::Block &B, size_t OpIdx, size_t Offset) {
+  auto InstAndSize = disassemble(Dis, B, Offset);
   if (!InstAndSize)
     return InstAndSize.takeError();
 
diff --git a/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h b/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h
index 8e1273ed911..5c90532d897 100644
--- a/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h
+++ b/llvm/unittests/ExecutionEngine/JITLink/JITLinkTestCommon.h
@@ -77,9 +77,9 @@ public:
 
   class TestJITLinkContext : public jitlink::JITLinkContext {
   public:
-    using TestCaseFunction = std::function<void(jitlink::AtomGraph &)>;
+    using TestCaseFunction = std::function<void(jitlink::LinkGraph &)>;
 
-    using NotifyResolvedFunction = std::function<void(jitlink::AtomGraph &G)>;
+    using NotifyResolvedFunction = std::function<void(jitlink::LinkGraph &G)>;
 
     using NotifyFinalizedFunction = std::function<void(
         std::unique_ptr<jitlink::JITLinkMemoryManager::Allocation>)>;
@@ -103,11 +103,11 @@ public:
 
     void notifyFailed(Error Err) override;
 
-    void
-    lookup(const DenseSet<StringRef> &Symbols,
-           jitlink::JITLinkAsyncLookupContinuation LookupContinuation) override;
+    void lookup(
+        const DenseSet<StringRef> &Symbols,
+        std::unique_ptr<jitlink::JITLinkAsyncLookupContinuation> LC) override;
 
-    void notifyResolved(jitlink::AtomGraph &G) override;
+    void notifyResolved(jitlink::LinkGraph &G) override;
 
     void notifyFinalized(
         std::unique_ptr<jitlink::JITLinkMemoryManager::Allocation> A) override;
@@ -140,56 +140,60 @@ public:
   }
 
   template <typename T>
-  static Expected<T> readInt(jitlink::AtomGraph &G, jitlink::DefinedAtom &A,
+  static Expected<T> readInt(jitlink::LinkGraph &G, jitlink::Block &B,
                              size_t Offset = 0) {
-    if (Offset + sizeof(T) > A.getContent().size())
-      return make_error<StringError>("Reading past end of atom content",
+    if (Offset + sizeof(T) > B.getSize())
+      return make_error<StringError>("Reading past end of block content",
                                      inconvertibleErrorCode());
-    return support::endian::read<T, 1>(A.getContent().data() + Offset,
+    return support::endian::read<T, 1>(B.getContent().data() + Offset,
                                        G.getEndianness());
   }
 
   template <typename T>
-  static Expected<T> readInt(jitlink::AtomGraph &G, StringRef AtomName,
+  static Expected<T> readInt(jitlink::LinkGraph &G, StringRef SymbolName,
                              size_t Offset = 0) {
-    auto DA = G.findDefinedAtomByName(AtomName);
-    if (!DA)
-      return DA.takeError();
-    return readInt<T>(G, *DA);
+    for (auto *Sym : G.defined_symbols()) {
+      if (Sym->getName() == SymbolName)
+        return readInt<T>(G, Sym->getBlock(), Sym->getOffset() + Offset);
+    }
+    return make_error<StringError>("Symbol \"" + SymbolName + "\" not found",
+                                   inconvertibleErrorCode());
   }
 
   static Expected<std::pair<MCInst, size_t>>
-  disassemble(const MCDisassembler &Dis, jitlink::DefinedAtom &Atom,
-              size_t Offset = 0);
+  disassemble(const MCDisassembler &Dis, jitlink::Block &B, size_t Offset = 0);
 
   static Expected<int64_t> decodeImmediateOperand(const MCDisassembler &Dis,
-                                                  jitlink::DefinedAtom &Atom,
+                                                  jitlink::Block &B,
                                                   size_t OpIdx,
                                                   size_t Offset = 0);
 
-  static jitlink::Atom &atom(jitlink::AtomGraph &G, StringRef Name) {
-    return G.getAtomByName(Name);
+  static jitlink::Symbol &symbol(jitlink::LinkGraph &G, StringRef Name) {
+    for (auto *Sym : G.defined_symbols())
+      if (Sym->getName() == Name)
+        return *Sym;
+    for (auto *Sym : G.external_symbols())
+      if (Sym->getName() == Name)
+        return *Sym;
+    for (auto *Sym : G.absolute_symbols())
+      if (Sym->getName() == Name)
+        return *Sym;
+    llvm_unreachable("Name must reference a symbol");
   }
 
-  static jitlink::DefinedAtom &definedAtom(jitlink::AtomGraph &G,
-                                           StringRef Name) {
-    return G.getDefinedAtomByName(Name);
-  }
-
-  static JITTargetAddress atomAddr(jitlink::AtomGraph &G, StringRef Name) {
-    return atom(G, Name).getAddress();
+  static JITTargetAddress symbolAddr(jitlink::LinkGraph &G, StringRef Name) {
+    return symbol(G, Name).getAddress();
   }
 
   template <typename PredT>
-  static size_t countEdgesMatching(jitlink::DefinedAtom &DA,
-                                   const PredT &Pred) {
-    return std::count_if(DA.edges().begin(), DA.edges().end(), Pred);
+  static size_t countEdgesMatching(jitlink::Block &B, const PredT &Pred) {
+    return std::count_if(B.edges().begin(), B.edges().end(), Pred);
   }
 
   template <typename PredT>
-  static size_t countEdgesMatching(jitlink::AtomGraph &G, StringRef Name,
+  static size_t countEdgesMatching(jitlink::LinkGraph &G, StringRef Name,
                                    const PredT &Pred) {
-    return countEdgesMatching(definedAtom(G, Name), Pred);
+    return countEdgesMatching(symbol(G, Name), Pred);
   }
 
 private:
diff --git a/llvm/unittests/ExecutionEngine/JITLink/MachO_x86_64_Tests.cpp b/llvm/unittests/ExecutionEngine/JITLink/MachO_x86_64_Tests.cpp
index e051ad551c7..9b76edae499 100644
--- a/llvm/unittests/ExecutionEngine/JITLink/MachO_x86_64_Tests.cpp
+++ b/llvm/unittests/ExecutionEngine/JITLink/MachO_x86_64_Tests.cpp
@@ -24,7 +24,7 @@ class JITLinkTest_MachO_x86_64 : public JITLinkTestCommon,
                                  public testing::Test {
 public:
   using BasicVerifyGraphFunction =
-      std::function<void(AtomGraph &, const MCDisassembler &)>;
+      std::function<void(LinkGraph &, const MCDisassembler &)>;
 
   void runBasicVerifyGraphTest(StringRef AsmSrc, StringRef Triple,
                                StringMap<JITEvaluatedSymbol> Externals,
@@ -40,7 +40,7 @@ public:
     }
 
     auto JTCtx = std::make_unique<TestJITLinkContext>(
-        **TR, [&](AtomGraph &G) { RunGraphTest(G, (*TR)->getDisassembler()); });
+        **TR, [&](LinkGraph &G) { RunGraphTest(G, (*TR)->getDisassembler()); });
 
     JTCtx->externals() = std::move(Externals);
 
@@ -48,78 +48,77 @@ public:
   }
 
 protected:
-  static void verifyIsPointerTo(AtomGraph &G, DefinedAtom &A, Atom &Target) {
-    EXPECT_EQ(A.edges_size(), 1U) << "Incorrect number of edges for pointer";
-    if (A.edges_size() != 1U)
+  static void verifyIsPointerTo(LinkGraph &G, Block &B, Symbol &Target) {
+    EXPECT_EQ(B.edges_size(), 1U) << "Incorrect number of edges for pointer";
+    if (B.edges_size() != 1U)
       return;
-    auto &E = *A.edges().begin();
+    auto &E = *B.edges().begin();
+    EXPECT_EQ(E.getOffset(), 0U) << "Expected edge offset of zero";
     EXPECT_EQ(E.getKind(), Pointer64)
         << "Expected pointer to have a pointer64 relocation";
     EXPECT_EQ(&E.getTarget(), &Target) << "Expected edge to point at target";
-    EXPECT_THAT_EXPECTED(readInt<uint64_t>(G, A), HasValue(Target.getAddress()))
+    EXPECT_THAT_EXPECTED(readInt<uint64_t>(G, B), HasValue(Target.getAddress()))
         << "Pointer does not point to target";
   }
 
-  static void verifyGOTLoad(AtomGraph &G, DefinedAtom &A, Edge &E,
-                            Atom &Target) {
+  static void verifyGOTLoad(LinkGraph &G, Edge &E, Symbol &Target) {
     EXPECT_EQ(E.getAddend(), 0U) << "Expected GOT load to have a zero addend";
     EXPECT_TRUE(E.getTarget().isDefined())
-        << "GOT entry should be a defined atom";
+        << "GOT entry should be a defined symbol";
     if (!E.getTarget().isDefined())
       return;
 
-    verifyIsPointerTo(G, static_cast<DefinedAtom &>(E.getTarget()), Target);
+    verifyIsPointerTo(G, E.getTarget().getBlock(), Target);
   }
 
-  static void verifyCall(const MCDisassembler &Dis, AtomGraph &G,
-                         DefinedAtom &Caller, Edge &E, Atom &Callee) {
+  static void verifyCall(const MCDisassembler &Dis, LinkGraph &G,
+                         Block &CallerBlock, Edge &E, Symbol &Callee) {
     EXPECT_EQ(E.getKind(), Branch32) << "Edge is not a Branch32";
     EXPECT_EQ(E.getAddend(), 0U) << "Expected no addend on stub call";
     EXPECT_EQ(&E.getTarget(), &Callee)
         << "Edge does not point at expected callee";
 
-    JITTargetAddress FixupAddress = Caller.getAddress() + E.getOffset();
+    JITTargetAddress FixupAddress = CallerBlock.getAddress() + E.getOffset();
     uint64_t PCRelDelta = Callee.getAddress() - (FixupAddress + 4);
 
     EXPECT_THAT_EXPECTED(
-        decodeImmediateOperand(Dis, Caller, 0, E.getOffset() - 1),
+        decodeImmediateOperand(Dis, CallerBlock, 0, E.getOffset() - 1),
         HasValue(PCRelDelta));
   }
 
-  static void verifyIndirectCall(const MCDisassembler &Dis, AtomGraph &G,
-                                 DefinedAtom &Caller, Edge &E, Atom &Callee) {
+  static void verifyIndirectCall(const MCDisassembler &Dis, LinkGraph &G,
+                                 Block &CallerBlock, Edge &E, Symbol &Callee) {
     EXPECT_EQ(E.getKind(), PCRel32) << "Edge is not a PCRel32";
     EXPECT_EQ(E.getAddend(), 0) << "Expected no addend on stub cal";
-    EXPECT_TRUE(E.getTarget().isDefined()) << "Target is not a defined atom";
+    EXPECT_TRUE(E.getTarget().isDefined()) << "Target is not a defined symbol";
     if (!E.getTarget().isDefined())
       return;
-    verifyIsPointerTo(G, static_cast<DefinedAtom &>(E.getTarget()), Callee);
+    verifyIsPointerTo(G, E.getTarget().getBlock(), Callee);
 
-    JITTargetAddress FixupAddress = Caller.getAddress() + E.getOffset();
+    JITTargetAddress FixupAddress = CallerBlock.getAddress() + E.getOffset();
     uint64_t PCRelDelta = E.getTarget().getAddress() - (FixupAddress + 4);
 
     EXPECT_THAT_EXPECTED(
-        decodeImmediateOperand(Dis, Caller, 3, E.getOffset() - 2),
+        decodeImmediateOperand(Dis, CallerBlock, 3, E.getOffset() - 2),
         HasValue(PCRelDelta));
   }
 
-  static void verifyCallViaStub(const MCDisassembler &Dis, AtomGraph &G,
-                                DefinedAtom &Caller, Edge &E, Atom &Callee) {
-    verifyCall(Dis, G, Caller, E, E.getTarget());
+  static void verifyCallViaStub(const MCDisassembler &Dis, LinkGraph &G,
+                                Block &CallerBlock, Edge &E, Symbol &Callee) {
+    verifyCall(Dis, G, CallerBlock, E, E.getTarget());
 
     if (!E.getTarget().isDefined()) {
       ADD_FAILURE() << "Edge target is not a stub";
       return;
     }
 
-    auto &StubAtom = static_cast<DefinedAtom &>(E.getTarget());
-    EXPECT_EQ(StubAtom.edges_size(), 1U)
+    auto &StubBlock = E.getTarget().getBlock();
+    EXPECT_EQ(StubBlock.edges_size(), 1U)
         << "Expected one edge from stub to target";
 
-    auto &StubEdge = *StubAtom.edges().begin();
+    auto &StubEdge = *StubBlock.edges().begin();
 
-    verifyIndirectCall(Dis, G, static_cast<DefinedAtom &>(StubAtom), StubEdge,
-                       Callee);
+    verifyIndirectCall(Dis, G, StubBlock, StubEdge, Callee);
   }
 };
 
@@ -161,24 +160,24 @@ TEST_F(JITLinkTest_MachO_x86_64, BasicRelocations) {
       {{"_y", JITEvaluatedSymbol(0xdeadbeef, JITSymbolFlags::Exported)},
        {"_baz", JITEvaluatedSymbol(0xcafef00d, JITSymbolFlags::Exported)}},
       true, false, MCTargetOptions(),
-      [](AtomGraph &G, const MCDisassembler &Dis) {
-        // Name the atoms in the asm above.
-        auto &Baz = atom(G, "_baz");
-        auto &Y = atom(G, "_y");
-
-        auto &Bar = definedAtom(G, "_bar");
-        auto &Foo = definedAtom(G, "_foo");
-        auto &Foo_1 = definedAtom(G, "_foo.1");
-        auto &Foo_2 = definedAtom(G, "_foo.2");
-        auto &X = definedAtom(G, "_x");
-        auto &P = definedAtom(G, "_p");
+      [](LinkGraph &G, const MCDisassembler &Dis) {
+        // Name the symbols in the asm above.
+        auto &Baz = symbol(G, "_baz");
+        auto &Y = symbol(G, "_y");
+        auto &Bar = symbol(G, "_bar");
+        auto &Foo = symbol(G, "_foo");
+        auto &Foo_1 = symbol(G, "_foo.1");
+        auto &Foo_2 = symbol(G, "_foo.2");
+        auto &X = symbol(G, "_x");
+        auto &P = symbol(G, "_p");
 
         // Check unsigned reloc for _p
         {
-          EXPECT_EQ(P.edges_size(), 1U) << "Unexpected number of relocations";
-          EXPECT_EQ(P.edges().begin()->getKind(), Pointer64)
+          EXPECT_EQ(P.getBlock().edges_size(), 1U)
+              << "Unexpected number of relocations";
+          EXPECT_EQ(P.getBlock().edges().begin()->getKind(), Pointer64)
               << "Unexpected edge kind for _p";
-          EXPECT_THAT_EXPECTED(readInt<uint64_t>(G, P),
+          EXPECT_THAT_EXPECTED(readInt<uint64_t>(G, P.getBlock()),
                                HasValue(X.getAddress()))
               << "Unsigned relocation did not apply correctly";
         }
@@ -188,41 +187,45 @@ TEST_F(JITLinkTest_MachO_x86_64, BasicRelocations) {
         // indirect call, and that the pointer for the indirect call points to
         // baz.
         {
-          EXPECT_EQ(Bar.edges_size(), 1U)
+          EXPECT_EQ(Bar.getBlock().edges_size(), 1U)
               << "Incorrect number of edges for bar";
-          EXPECT_EQ(Bar.edges().begin()->getKind(), Branch32)
+          EXPECT_EQ(Bar.getBlock().edges().begin()->getKind(), Branch32)
               << "Unexpected edge kind for _bar";
-          verifyCallViaStub(Dis, G, Bar, *Bar.edges().begin(), Baz);
+          verifyCallViaStub(Dis, G, Bar.getBlock(),
+                            *Bar.getBlock().edges().begin(), Baz);
         }
 
         // Check that _foo is a direct call to _bar.
         {
-          EXPECT_EQ(Foo.edges_size(), 1U)
+          EXPECT_EQ(Foo.getBlock().edges_size(), 1U)
               << "Incorrect number of edges for foo";
-          EXPECT_EQ(Foo.edges().begin()->getKind(), Branch32);
-          verifyCall(Dis, G, Foo, *Foo.edges().begin(), Bar);
+          EXPECT_EQ(Foo.getBlock().edges().begin()->getKind(), Branch32);
+          verifyCall(Dis, G, Foo.getBlock(), *Foo.getBlock().edges().begin(),
+                     Bar);
         }
 
         // Check .got load in _foo.1
         {
-          EXPECT_EQ(Foo_1.edges_size(), 1U)
+          EXPECT_EQ(Foo_1.getBlock().edges_size(), 1U)
               << "Incorrect number of edges for foo_1";
-          EXPECT_EQ(Foo_1.edges().begin()->getKind(), PCRel32);
-          verifyGOTLoad(G, Foo_1, *Foo_1.edges().begin(), Y);
+          EXPECT_EQ(Foo_1.getBlock().edges().begin()->getKind(), PCRel32);
+          verifyGOTLoad(G, *Foo_1.getBlock().edges().begin(), Y);
         }
 
         // Check PCRel ref to _p in _foo.2
         {
-          EXPECT_EQ(Foo_2.edges_size(), 1U)
+          EXPECT_EQ(Foo_2.getBlock().edges_size(), 1U)
               << "Incorrect number of edges for foo_2";
-          EXPECT_EQ(Foo_2.edges().begin()->getKind(), PCRel32);
+          EXPECT_EQ(Foo_2.getBlock().edges().begin()->getKind(), PCRel32);
 
           JITTargetAddress FixupAddress =
-              Foo_2.getAddress() + Foo_2.edges().begin()->getOffset();
+              Foo_2.getBlock().getAddress() +
+              Foo_2.getBlock().edges().begin()->getOffset();
           uint64_t PCRelDelta = P.getAddress() - (FixupAddress + 4);
 
-          EXPECT_THAT_EXPECTED(decodeImmediateOperand(Dis, Foo_2, 4, 0),
-                               HasValue(PCRelDelta))
+          EXPECT_THAT_EXPECTED(
+              decodeImmediateOperand(Dis, Foo_2.getBlock(), 4, 0),
+              HasValue(PCRelDelta))
               << "PCRel load does not reference expected target";
         }
       });