[JITLink] Factor out forEachRelocation() function from addRelocations() in ELF Aarch64 backend (NFC)

[sgraenitz]

Summary

This patch is a first step in reducing redundancy in addRelocations() implementations across ELF JITLink backends. It factors out common logic for ELF relocation traversal into the new helper function forEachRelocation() in the ELFLinkGraphBuilder base class.

[sgraenitz]

As discussed in D108986. Furthermore the patch:

• aligns the format of debug output with the MachO implementation (seemed more comprehensible)
• aims to be NFC otherwise -- ping me if I introduced a functional change by accident
• replaces auto with concrete type names where they aren't obvious or irrelevant
• tries to use more consistent names

[lhames]

Thanks very much for this Stefan!

Is there a reason that forEachRelocation works one-section-at-a-time? I thought that forEachRelocation could embed the loop over the sections within it to simplify addRelocations further. I.e. in most cases it should reduce to something like:

Error addRelocations() override {
  LLVM_DEBUG(dbgs() << "Processing relocations:\n");
  return forEachRelocation(RelSect, this, &ELFJITLinker_aarch64::addSingleRelocation);
}

There may be a good reason not to do that in ELF though?

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

113–118

I think forEachRelocation should be a template method here, rather than taking a std::function:

/// Func should be callable as:
///   Error(const typename ELFT::Rela &,
///         const typename ELFT::Shdr &, Section &)

template <typename RelocHandlerFunction>
Error forEachRelocation(const typename ELFT::Shdr &RelSect,
                        RelocHandlerFunction &&Func, bool ProcessDebugSections) {
  ...
}

It might be handy to provide a method version for convenience too:

template <typename ClassT, typename RelocHandlerMethod>
Error forEachRelocation(const typename ELFT::Shdr &RelSect,
                        ClassT *Instance, RelocHandlerMethod *Method,
                        bool ProcessDebugSections) {
  return forEachRelocation(
      RelSect,
      [Instance, Method](const typename ELFT::Rela &Rel,
                         const typename ELFT::Shdr &Target,
                         Section &GS) {
        return (Instance->*Method)(Rel, Target, GS);
      },
      ProcessDebugSections);
}

With that, I think the iteration below could be reduced to:

using Base = ELFLinkGraphBuilder<ELFT>;
for (const auto &RelSect : Base::Sections)
  if (Error Err =
        Base::forEachRelocation(RelSect, this,
                                &ELFJITLinker_aarch64::addSingleRelocation))
    return Err;

[sgraenitz]

Turn std::function into template parameter

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

113–118

Agree, that's much better!

[sgraenitz]

In D109516#2995913, @lhames wrote:

Is there a reason that forEachRelocation works one-section-at-a-time? I thought that forEachRelocation could embed the loop over the sections within it to simplify addRelocations further.

I started like this and then realized that the x86_64 backend does an additional check on the type of the relocation section: https://github.com/llvm/llvm-project/blob/15e9575fb5988a66aa6e57a55818b54b575dd795/llvm/lib/ExecutionEngine/JITLink/ELF_x86_64.cpp#L217 Not sure if this specific use-case is really relevant, but I started thinking it might be worth having this option. (Especially since, logically, this loop doesn't add any value to the forEachRelocation function.)

Thinking again now: Assuming we skip most sections immediately, this probably adds unreasonable overhead. Because now there's 2 function calls before checking the type against ELF::SHT_REL(A). And there's not much hope for inlining even with the templated parameter, right? Would be really bad with -ffunction-sections.

So, yes for performance reasons I'd change that and put the loop back inside. @lhames What do you think?

[lhames]

In D109516#2996242, @sgraenitz wrote:

Thinking again now: Assuming we skip most sections immediately, this probably adds unreasonable overhead. Because now there's 2 function calls before checking the type against ELF::SHT_REL(A). And there's not much hope for inlining even with the templated parameter, right? Would be really bad with -ffunction-sections.

So, yes for performance reasons I'd change that and put the loop back inside. @lhames What do you think?

Thanks for making these changes Stefan. I'm happy with that approach. I think we would need to do some profiling to determine the practical performance impacts of these decisions before we bothered tuning further.

Now for a fun digression (only tangentially related to this, so you can skip it if you're busy): My motivation for asking you to remove the std::function was my intuition was that it would block inlining of the call to the per-relocation handling method. I didn't have any hard evidence to back that intuition up though, so for fun I thought I would write a quick test. In this test I let 'ints' stand in for relocation objects, since they should make things as easy as possible for the inliner:

#include <functional>

void doSomethingWith(int);

class MyLinker {
public:
  void handleRelocation(int X) { doSomethingWith(X); }
};


template <typename Func>
void functionObjectWalk(const int *V, Func F) {
  while (*V != 0)
    F(*V++);
}

template <typename ClassT, typename MethT>
void methodWalk(const int *V, ClassT *Instance, MethT Method) {
  functionObjectWalk(V,
                     [Instance, Method](int X) {
                       (Instance->*Method)(X);
                     });
}

void stdfunctionWalk(const int *V,
                     std::function<void(int)> F) {
  while (*V != 0)
    F(*V++);
}

void testFunctionObjectWalk() {
  MyLinker ML;
  int V[] = { 1, 2, 3, 0 };
  functionObjectWalk(V, [&](int X) { ML.handleRelocation(X); });
}

void testMethodWalk() {
  MyLinker ML;
  int V[] = { 1, 2, 3, 0 };
  methodWalk(V, &ML, &MyLinker::handleRelocation);
}

void testStdFunctionWalk() {
  MyLinker ML;
  int V[] = { 1, 2, 3, 0 };
  stdfunctionWalk(V, [&](int X) { ML.handleRelocation(X); });
}

I compiled this with a released Xcode clang with: clang++ -std=c++17 -fno-exceptions -fno-rtti -fno-asynchronous-unwind-tables -O3 -S -o testcase.s testcase.cpp (the options helped to keep the assembly readable). As expected: functionObjectWalk and methodWalk produce equivalent results with neatly inlined calls to doSomethingWith, whereas stdfunctionWalk produces a longer loop with an indirect call. I'm going to call my intuition "tentatively confirmed". I'm not quite motivated enough to dig into the assembly for a release build of LLVM at the moment. ;)

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

protected:
 
   Expected<std::pair<Linkage, Scope>>
   getSymbolLinkageAndScope(const typename ELFT::Sym &Sym, StringRef Name);
 
   Error prepare();
   Error graphifySections();
   Error graphifySymbols();
 
+  /// Traverse all matching relocation records in the given section. The handler
+  /// function Func should be callable with this signature:
+  ///   Error(const typename ELFT::Rela &,
+  ///         const typename ELFT::Shdr &, Section &)
+  ///
+  template <typename RelocHandlerFunction>
+  Error forEachRelocation(const typename ELFT::Shdr &RelSect,
+                          RelocHandlerFunction &&Func,
+                          bool ProcessDebugSections = false);
+
+  /// Traverse all matching relocation records in the given section. Convenience
+  /// wrapper to allow passing a member function for the handler.
+  ///
+  template <typename ClassT, typename RelocHandlerMethod>
+  Error forEachRelocation(const typename ELFT::Shdr &RelSect, ClassT *Instance,
+                          RelocHandlerMethod &&Method,
+                          bool ProcessDebugSections = false) {
+    return forEachRelocation(
+        RelSect,
+        [Instance, Method](const auto &Rel, const auto &Target, auto &GS) {
+          return (Instance->*Method)(Rel, Target, GS);
+        },
+        ProcessDebugSections);
+  }
+
   const ELFFile &Obj;
 
   typename ELFFile::Elf_Shdr_Range Sections;
   const typename ELFFile::Elf_Shdr *SymTabSec = nullptr;
   StringRef SectionStringTab;
 
   // Maps ELF section indexes to LinkGraph Sections.
   // Only SHF_ALLOC sections will have graph sections.
if (Sym.isDefined() &&
                << "\" with unrecognized type\n";
       });
     }
   }
 
   return Error::success();
 }
 
+template <typename ELFT>
+template <typename RelocHandlerFunction>
+Error ELFLinkGraphBuilder<ELFT>::forEachRelocation(
+    const typename ELFT::Shdr &RelSect, RelocHandlerFunction &&Func,
+    bool ProcessDebugSections) {
+
+  // Only look into sections that store relocation entries.
+  if (RelSect.sh_type != ELF::SHT_RELA && RelSect.sh_type != ELF::SHT_REL)
+    return Error::success();
+
+  // sh_info contains the section header index of the target (FixupSection),
+  // which is the section to which all relocations in RelSect apply.
+  auto FixupSection = Obj.getSection(RelSect.sh_info);
+  if (!FixupSection)
+    return FixupSection.takeError();
+
+  // Target sections have names in valid ELF object files.
+  Expected<StringRef> Name = Obj.getSectionName(**FixupSection);
+  if (!Name)
+    return Name.takeError();
+  LLVM_DEBUG(dbgs() << "  " << *Name << ":\n");
+
+  // Consider skipping these relocations.
+  if (!ProcessDebugSections && isDwarfSection(*Name)) {
+    LLVM_DEBUG(dbgs() << "    skipped (dwarf section)\n\n");
+    return Error::success();
+  }
+
+  // Lookup the link-graph node corresponding to the target section name.
+  Section *GraphSect = G->findSectionByName(*Name);
+  if (!GraphSect)
+    return make_error<StringError>(
+        "Refencing a section that wasn't added to the graph: " + *Name,
+        inconvertibleErrorCode());
+
+  auto RelEntries = Obj.relas(RelSect);
+  if (!RelEntries)
+    return RelEntries.takeError();
+
+  // Let the callee process relocation entries one by one.
+  for (const typename ELFT::Rela &R : *RelEntries)
+    if (Error Err = Func(R, **FixupSection, *GraphSect))
+      return Err;
+
+  LLVM_DEBUG(dbgs() << "\n");
+  return Error::success();
+}
+
 } // end namespace jitlink
 } // end namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif // LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H

llvm/lib/ExecutionEngine/JITLink/ELF_aarch64.cpp

case ELF::R_AARCH64_CALL26:
       return EdgeKind_aarch64::R_AARCH64_CALL26;
     }
 
     return make_error<JITLinkError>("Unsupported aarch64 relocation:" +
                                     formatv("{0:d}", Type));
   }
 
   Error addRelocations() override {
-    using Base = ELFLinkGraphBuilder<ELFT>;
-    LLVM_DEBUG(dbgs() << "Adding relocations\n");
-
-    // Iterate sections and only process the interesting ones.
-    for (auto &SecRef : Base::Sections) {
-      if (SecRef.sh_type != ELF::SHT_RELA && SecRef.sh_type != ELF::SHT_REL)
-        continue;
-      auto RelSectName = Base::Obj.getSectionName(SecRef);
-      if (!RelSectName)
-        return RelSectName.takeError();
-
-      LLVM_DEBUG({
-        dbgs() << "Adding relocations from section " << *RelSectName << "\n";
-      });
+    LLVM_DEBUG(dbgs() << "Processing relocations:\n");
 
-      auto UpdateSect = Base::Obj.getSection(SecRef.sh_info);
-      if (!UpdateSect)
-        return UpdateSect.takeError();
-
-      auto UpdateSectName = Base::Obj.getSectionName(**UpdateSect);
-      if (!UpdateSectName)
-        return UpdateSectName.takeError();
+    using Base = ELFLinkGraphBuilder<ELFT>;
+    using Self = ELFLinkGraphBuilder_aarch64<ELFT>;
+    for (const auto &RelSect : Base::Sections)
+      if (Error Err = Base::forEachRelocation(RelSect, this,
+                                              &Self::addSingleRelocation))
+        return Err;
 
-      // Don't process relocations for debug sections.
-      if (Base::isDwarfSection(*UpdateSectName)) {
-        LLVM_DEBUG({
-          dbgs() << "  Target is dwarf section " << *UpdateSectName
-                 << ". Skipping.\n";
-        });
-        continue;
-      }
-      LLVM_DEBUG(dbgs() << "  For target section " << *UpdateSectName << "\n");
-
-      auto *JITSection = Base::G->findSectionByName(*UpdateSectName);
-      if (!JITSection)
-        return make_error<llvm::StringError>(
-            "Refencing a section that wasn't added to graph" + *UpdateSectName,
-            llvm::inconvertibleErrorCode());
-
-      auto Relocations = Base::Obj.relas(SecRef);
-      if (!Relocations)
-        return Relocations.takeError();
+    return Error::success();
 
-      for (const auto &Rela : *Relocations) {
-        auto Type = Rela.getType(false);
+  Error addSingleRelocation(const typename ELFT::Rela &Rel,
+                            const typename ELFT::Shdr &FixupSect,
+                            Section &GraphSection) {
+    using Base = ELFLinkGraphBuilder<ELFT>;
 
-        LLVM_DEBUG({
-          dbgs() << "Relocation Type: " << Type << "\n"
-                 << "Name: " << Base::Obj.getRelocationTypeName(Type) << "\n";
-        });
+    uint32_t SymbolIndex = Rel.getSymbol(false);
+    auto ObjSymbol = Base::Obj.getRelocationSymbol(Rel, Base::SymTabSec);
+    if (!ObjSymbol)
+      return ObjSymbol.takeError();
+
+    Symbol *GraphSymbol = Base::getGraphSymbol(SymbolIndex);
+    if (!GraphSymbol)
+      return make_error<StringError>(
+          formatv("Could not find symbol at given index, did you add it to "
+                  "JITSymbolTable? index: {0}, shndx: {1} Size of table: {2}",
+                  SymbolIndex, (*ObjSymbol)->st_shndx,
+                  Base::GraphSymbols.size()),
+          inconvertibleErrorCode());
 
-        auto SymbolIndex = Rela.getSymbol(false);
-        auto Symbol = Base::Obj.getRelocationSymbol(Rela, Base::SymTabSec);
-        if (!Symbol)
-          return Symbol.takeError();
-
-        auto BlockToFix = *(JITSection->blocks().begin());
-        auto *TargetSymbol = Base::getGraphSymbol(SymbolIndex);
-
-        if (!TargetSymbol) {
-          return make_error<llvm::StringError>(
-              "Could not find symbol at given index, did you add it to "
-              "JITSymbolTable? index: " +
-                  std::to_string(SymbolIndex) + ", shndx: " +
-                  std::to_string((*Symbol)->st_shndx) + " Size of table: " +
-                  std::to_string(Base::GraphSymbols.size()),
-              llvm::inconvertibleErrorCode());
-        }
-        int64_t Addend = Rela.r_addend;
-        JITTargetAddress FixupAddress = (*UpdateSect)->sh_addr + Rela.r_offset;
+    uint32_t Type = Rel.getType(false);
+    Expected<aarch64::EdgeKind_aarch64> Kind = getRelocationKind(Type);
+    if (!Kind)
+      return Kind.takeError();
 
-        LLVM_DEBUG({
-          dbgs() << "Processing relocation at "
-                 << format("0x%016" PRIx64, FixupAddress) << "\n";
-        });
-        auto Kind = getRelocationKind(Type);
-        if (!Kind)
-          return Kind.takeError();
+    int64_t Addend = Rel.r_addend;
+    Block *BlockToFix = *(GraphSection.blocks().begin());
+    JITTargetAddress FixupAddress = FixupSect.sh_addr + Rel.r_offset;
+    Edge::OffsetT Offset = FixupAddress - BlockToFix->getAddress();
+    Edge GE(*Kind, Offset, *GraphSymbol, Addend);
+      dbgs() << "    ";
+      printEdge(dbgs(), *BlockToFix, GE, aarch64::getEdgeKindName(*Kind));
+      dbgs() << "\n";
 
-        BlockToFix->addEdge(*Kind, FixupAddress - BlockToFix->getAddress(),
-                            *TargetSymbol, Addend);
-      }
-    }
+    BlockToFix->addEdge(std::move(GE));
     return Error::success();
   }
 
 public:
   ELFLinkGraphBuilder_aarch64(StringRef FileName,
                               const object::ELFFile<ELFT> &Obj, const Triple T)
       : ELFLinkGraphBuilder<ELFT>(Obj, std::move(T), FileName,
                                   aarch64::getEdgeKindName) {}