[JITLink] Allow edges without a target

[jobnoorman]

Summary

Certain relocations do not use a target symbol. Examples of this are
R_RISCV_RELAX (which is just used to mark another relocation as
relaxable) and R_RISCV_ALIGN (which encodes an alignment requirement in
its addend). This patch makes sure such relocations can be represented
in an Edge.

[lhames]

Hi Job,

I believe we can handle R_RISCV_RELAX and R_RISCV_ALIGN without changing Edge -- it would be great to keep "Edges always have targets" as a simple invariants if we can.

For R_RISCV_RELAX we should add relaxable edge kinds to the RISCV edge kinds enum (along the same lines as the x86-64 relaxable edges, and we should take this opportunity to rename the RISCV edges to bring them in line with the other architectures). When the ELF/RISCV LinkGraphBuilder sees an R_RISCV_RELAX relocation it should choose the relaxable variant for the corresponding edge.

For R_RISCV_ALIGN I think we can reasonably just point the Edge at a null absolute symbol.

[jobnoorman]

Hi Lang,

In D149524#4308261, @lhames wrote:

I believe we can handle R_RISCV_RELAX and R_RISCV_ALIGN without changing Edge -- it would be great to keep "Edges always have targets" as a simple invariants if we can.

Yes, I agree. I found all the !hasTarget() checks this patch had to add quite inelegant.

For R_RISCV_RELAX we should add relaxable edge kinds to the RISCV edge kinds enum (along the same lines as the x86-64 relaxable edges, and we should take this opportunity to rename the RISCV edges to bring them in line with the other architectures). When the ELF/RISCV LinkGraphBuilder sees an R_RISCV_RELAX relocation it should choose the relaxable variant for the corresponding edge.

This looks like a very interesting approach! I'll look into it next week. For now, I used the same null symbol approach as for R_RISCV_ALIGN.

For R_RISCV_ALIGN I think we can reasonably just point the Edge at a null absolute symbol.

Interestingly, both R_RISCV_ALIGN and R_RISCV_RELAX actually point to some kind of null symbol in the ELF file. It's an undefined symbol (UND) though and in an earlier attempt, I actually tried to add this symbol to the LinkGraph as some kind of new symbol type (local undefined). However, this had a huge ripple effect so I abandoned that approach for the one in this patch. Using an absolute symbol instead works quite nicely without a large fallout. Thanks for this idea! I created D149541 for this.

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

enum GenericEdgeKind : Kind {
     FirstRelocation             // First architecture specific relocation.
   };
 
   using OffsetT = uint32_t;
   using AddendT = int64_t;
 
   Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
       : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}
+  Edge(Kind K, OffsetT Offset, AddendT Addend)
+      : Offset(Offset), Addend(Addend), K(K) {}
 
   OffsetT getOffset() const { return Offset; }
   void setOffset(OffsetT Offset) { this->Offset = Offset; }
   Kind getKind() const { return K; }
   void setKind(Kind K) { this->K = K; }
   bool isRelocation() const { return K >= FirstRelocation; }
   Kind getRelocation() const {
     assert(isRelocation() && "Not a relocation edge");
     return K - FirstRelocation;
   }
   bool isKeepAlive() const { return K >= FirstKeepAlive; }
-  Symbol &getTarget() const { return *Target; }
+  bool hasTarget() const { return Target != nullptr; }
+  Symbol &getTarget() const {
+    assert(Target && "Not an edge with a target");
+    return *Target;
+  }
   void setTarget(Symbol &Target) { this->Target = &Target; }
   AddendT getAddend() const { return Addend; }
   void setAddend(AddendT Addend) { this->Addend = Addend; }
 
 private:
   Symbol *Target = nullptr;
   OffsetT Offset = 0;
   AddendT Addend = 0;

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

OS << Sym.getAddress() << " (" << (Sym.isDefined() ? "block" : "addressable")
      << (Sym.isLive() ? "live" : "dead") << "  -   "
      << (Sym.hasName() ? Sym.getName() : "<anonymous symbol>");
   return OS;
 }
 
 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
                StringRef EdgeKindName) {
   OS << "edge@" << B.getAddress() + E.getOffset() << ": " << B.getAddress()
-     << " + " << formatv("{0:x}", E.getOffset()) << " -- " << EdgeKindName
-     << " -> ";
+     << " + " << formatv("{0:x}", E.getOffset()) << " -- " << EdgeKindName;
+
+  if (!E.hasTarget()) {
+    OS << " (no target, addend " << E.getAddend() << ")";
+    return;
+  }
+
+  OS << " -> ";
 
   auto &TargetSym = E.getTarget();
   if (TargetSym.hasName())
     OS << TargetSym.getName();
   else {
     auto &TargetBlock = TargetSym.getBlock();
     auto &TargetSec = TargetBlock.getSection();
     orc::ExecutorAddr SecAddress(~uint64_t(0));
for (auto *B : SortedBlocks) {
         });
         for (auto &E : SortedEdges) {
           OS << "      " << B->getFixupAddress(E) << " (block + "
              << formatv("{0:x8}", E.getOffset()) << "), addend = ";
           if (E.getAddend() >= 0)
             OS << formatv("+{0:x8}", E.getAddend());
           else
             OS << formatv("-{0:x8}", -E.getAddend());
-          OS << ", kind = " << getEdgeKindName(E.getKind()) << ", target = ";
+          OS << ", kind = " << getEdgeKindName(E.getKind());
+          if (E.hasTarget()) {
+            OS << ", target = ";
             if (E.getTarget().hasName())
               OS << E.getTarget().getName();
             else
               OS << "addressable@"
                  << formatv("{0:x16}", E.getTarget().getAddress()) << "+"
                  << formatv("{0:x8}", E.getTarget().getOffset());
+          }
           OS << "\n";
         }
       } else
         OS << "    no edges\n";
       OS << "\n";
     }
   }
 

llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.h

for (auto &Sec : G.sections()) {
         // memory allocated on the Graph's allocator (if it hasn't been
         // already).
         if (NoAllocSection)
           (void)B->getMutableContent(G);
 
         for (auto &E : B->edges()) {
 
           // Skip non-relocation edges.
-          if (!E.isRelocation())
+          if (!E.isRelocation() || !E.hasTarget())
             continue;
 
           // If B is a block in a Standard or Finalize section then make sure
           // that no edges point to symbols in NoAlloc sections.
           assert(
               (NoAllocSection || !E.getTarget().isDefined() ||
                E.getTarget().getBlock().getSection().getMemLifetimePolicy() !=
                    orc::MemLifetimePolicy::NoAlloc) &&

llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp

while (!Worklist.empty()) {
 
     // Skip addressables that we've visited before.
     if (VisitedBlocks.count(&B))
       continue;
 
     VisitedBlocks.insert(&B);
 
     for (auto &E : Sym->getBlock().edges()) {
+      if (!E.hasTarget())
+        continue;
+
       // If the edge target is a defined symbol that is being newly marked live
       // then add it to the worklist.
       if (E.getTarget().isDefined() && !E.getTarget().isLive())
         Worklist.push_back(&E.getTarget());
 
       // Mark the target live.
       E.getTarget().setLive(true);
     }

llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp

BlockDependenciesMap computeBlockNonLocalDeps(LinkGraph &G) {
     for (auto *B : G.blocks())
       (void)BlockInfos[B];
 
     // Build initial worklist, record block dependencies/dependants and
     // non-local symbol dependencies.
     for (auto *B : G.blocks()) {
       auto &BI = BlockInfos[B];
       for (auto &E : B->edges()) {
+        if (!E.hasTarget())
+          continue;
         if (E.getTarget().getScope() == Scope::Local &&
             !E.getTarget().isAbsolute()) {
           auto &TgtB = E.getTarget().getBlock();
           if (&TgtB != B) {
             BI.Dependencies.insert(&TgtB);
             BlockInfos[&TgtB].Dependants.insert(B);
           }
         }