[ELF] Add RelocationScanner. NFC

[MaskRay]

Summary

Currently the way some relocation-related static functions pass around
states is clumsy. Add a Resolver class to store some states as member
variables.

Advantages:

• Avoid the parameter InputSectionBase &sec (this offsets the cost passing around this paramemter)
• Avoid the parameter end (Mips and PowerPC hacks)
• config and target can be cached as member variables to reduce global state accesses. (potential speedup because the compiler didn't know config/target were not changed across function calls)
• If we ever want to reduce if-else costs (e.g. config->emachine==EM_MIPS for non-Mips) or introduce parallel relocation scan not handling some tricky arches (PPC/Mips)[1], we can templatize Resolver

target isn't used as much as config, so I change it to a const reference
during the migration.

There is a minor performance inprovement for elf::scanRelocations.

[1]: https://maskray.me/blog/2021-12-19-why-isnt-ld.lld-faster "Scan relocations"

[ikudrin]

lld/ELF/Relocations.cpp

434

i should be changed to something more self-explanatory. Or, maybe, OffsetGetter should be preserved as a separate class because it implements isolated functionality.

1294

Why config->isMips64EL is changed to 0?

[peter.smith]

In principle I'm in favour of having a class with a single public entry point. I agree with ikudrin's comments.

lld/ELF/Relocations.cpp

407

I normally think of resolving a relocation when the final value is written. Given that the only public member function is called scanRelocs. Perhaps call the class Scanner or RelocationScanner the latter is more verbose but we could use scan instead of scanRelocs.

Regardless of what the name is, it will be good to have a comment to describe this large class.

[MaskRay]

Rename to RelocationScanner. Rebase.

The instructions are fewer. Possible minor speed-up:

% hyperfine --warmup 2 --min-runs 40 "numactl -C 20-23 "{/tmp/c/0,/tmp/c/1}" -flavor gnu @response.txt --threads=4 -o lld.8"
Benchmark 1: numactl -C 20-23 /tmp/c/0 -flavor gnu @response.txt --threads=4 -o lld.8
  Time (mean ± σ):      1.311 s ±  0.015 s    [User: 1.360 s, System: 0.502 s]
  Range (min … max):    1.281 s …  1.339 s    40 runs
 
Benchmark 2: numactl -C 20-23 /tmp/c/1 -flavor gnu @response.txt --threads=4 -o lld.8
  Time (mean ± σ):      1.297 s ±  0.012 s    [User: 1.347 s, System: 0.497 s]
  Range (min … max):    1.279 s …  1.333 s    40 runs
 
Summary
  'numactl -C 20-23 /tmp/c/1 -flavor gnu @response.txt --threads=4 -o lld.8' ran
    1.01 ± 0.01 times faster than 'numactl -C 20-23 /tmp/c/0 -flavor gnu @response.txt --threads=4 -o lld.8'

[MaskRay]

lld/ELF/Relocations.cpp

407

Changed to RelocationScanner. I do not remember how I picked Resolver...

1294

Fixed.

It was unintentional - I was testing how mips checks affect the performance.

@atanasyan There is missing coverage for mips64el.

[MaskRay]

simplify

[ikudrin]

LGTM

[peter.smith]

LGTM too, thanks for the updates.

lld/ELF/Relocations.cpp

case ELF64BEKind:
     addCopyRelSymbolImpl<ELF64BE>(ss);
     break;
   default:
     llvm_unreachable("");
   }
 }
 
 // .eh_frame sections are mergeable input sections, so their input
 // offsets are not linearly mapped to output section. For each input
 // offset, we need to find a section piece containing the offset and
 // add the piece's base address to the input offset to compute the
 // output offset. That isn't cheap.
 //
 // This class is to speed up the offset computation. When we process
 // relocations, we access offsets in the monotonically increasing
 // order. So we can optimize for that access pattern.
 //
public:
   // Given offset must increase monotonically. We assume that Piece is
   // sorted by inputOff.
   uint64_t get(uint64_t off) {
     if (pieces.empty())
       return off;
 
     while (i != pieces.size() && pieces[i].inputOff + pieces[i].size <= off)
       ++i;
     if (i == pieces.size())
       fatal(".eh_frame: relocation is not in any piece");
 
     // Pieces must be contiguous, so there must be no holes in between.
     assert(pieces[i].inputOff <= off && "Relocation not in any piece");
 
     // Offset -1 means that the piece is dead (i.e. garbage collected).
     if (pieces[i].outputOff == -1)
       return -1;
     return pieces[i].outputOff + off - pieces[i].inputOff;
   }
 
 private:
   ArrayRef<EhSectionPiece> pieces;
   size_t i = 0;
 };
+
+// This class encapsulates states needed to scan relocations for one
+// InputSectionBase.
+class RelocationScanner {
+public:
+  explicit RelocationScanner(InputSectionBase &sec)
+      : sec(sec), getter(sec), config(elf::config.get()), target(*elf::target) {
+  }
+  template <class ELFT, class RelTy> void scan(ArrayRef<RelTy> rels);
+
+private:
+  InputSectionBase &sec;
+  OffsetGetter getter;
+  const Configuration *const config;
+  const TargetInfo &target;
+
+  // End of relocations, used by Mips/PPC64.
+  const void *end = nullptr;
+
+  template <class RelTy> RelType getMipsN32RelType(RelTy *&rel) const;
+  template <class ELFT, class RelTy>
+  int64_t computeMipsAddend(const RelTy &rel, RelExpr expr, bool isLocal) const;
+  template <class ELFT, class RelTy>
+  int64_t computeAddend(const RelTy &rel, RelExpr expr, bool isLocal) const;
+  bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym,
+                                uint64_t relOff) const;
+  void processAux(RelExpr expr, RelType type, uint64_t offset, Symbol &sym,
+                  int64_t addend) const;
+  template <class ELFT, class RelTy> void scanOne(RelTy *&i);
+};
 } // namespace
 
 // MIPS has an odd notion of "paired" relocations to calculate addends.
 // For example, if a relocation is of R_MIPS_HI16, there must be a
 // R_MIPS_LO16 relocation after that, and an addend is calculated using
 // the two relocations.
 template <class ELFT, class RelTy>
-static int64_t computeMipsAddend(const RelTy &rel, const RelTy *end,
-                                 InputSectionBase &sec, RelExpr expr,
-                                 bool isLocal) {
+int64_t RelocationScanner::computeMipsAddend(const RelTy &rel, RelExpr expr,
+                                             bool isLocal) const {
   if (expr == R_MIPS_GOTREL && isLocal)
     return sec.getFile<ELFT>()->mipsGp0;
 
   // The ABI says that the paired relocation is used only for REL.
   // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
   if (RelTy::IsRela)
     return 0;
 
   RelType type = rel.getType(config->isMips64EL);
   uint32_t pairTy = getMipsPairType(type, isLocal);
   if (pairTy == R_MIPS_NONE)
     return 0;
 
   const uint8_t *buf = sec.data().data();
   uint32_t symIndex = rel.getSymbol(config->isMips64EL);
 
   // To make things worse, paired relocations might not be contiguous in
   // the relocation table, so we need to do linear search. *sigh*
-  for (const RelTy *ri = &rel; ri != end; ++ri)
+  for (const RelTy *ri = &rel; ri != static_cast<const RelTy *>(end); ++ri)
     if (ri->getType(config->isMips64EL) == pairTy &&
         ri->getSymbol(config->isMips64EL) == symIndex)
-      return target->getImplicitAddend(buf + ri->r_offset, pairTy);
+      return target.getImplicitAddend(buf + ri->r_offset, pairTy);
 
   warn("can't find matching " + toString(pairTy) + " relocation for " +
        toString(type));
   return 0;
 }
 
 // Returns an addend of a given relocation. If it is RELA, an addend
 // is in a relocation itself. If it is REL, we need to read it from an
 // input section.
 template <class ELFT, class RelTy>
-static int64_t computeAddend(const RelTy &rel, const RelTy *end,
-                             InputSectionBase &sec, RelExpr expr,
-                             bool isLocal) {
+int64_t RelocationScanner::computeAddend(const RelTy &rel, RelExpr expr,
+                                         bool isLocal) const {
   int64_t addend;
   RelType type = rel.getType(config->isMips64EL);
 
   if (RelTy::IsRela) {
     addend = getAddend<ELFT>(rel);
   } else {
     const uint8_t *buf = sec.data().data();
-    addend = target->getImplicitAddend(buf + rel.r_offset, type);
+    addend = target.getImplicitAddend(buf + rel.r_offset, type);
   }
 
   if (config->emachine == EM_PPC64 && config->isPic && type == R_PPC64_TOC)
     addend += getPPC64TocBase();
   if (config->emachine == EM_MIPS)
-    addend += computeMipsAddend<ELFT>(rel, end, sec, expr, isLocal);
+    addend += computeMipsAddend<ELFT>(rel, expr, isLocal);
 
   return addend;
 }
 
 // Custom error message if Sym is defined in a discarded section.
 template <class ELFT>
 static std::string maybeReportDiscarded(Undefined &sym) {
   auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file);
static bool maybeReportUndefined(Symbol &sym, InputSectionBase &sec,
   return !isWarning;
 }
 
 // MIPS N32 ABI treats series of successive relocations with the same offset
 // as a single relocation. The similar approach used by N64 ABI, but this ABI
 // packs all relocations into the single relocation record. Here we emulate
 // this for the N32 ABI. Iterate over relocation with the same offset and put
 // theirs types into the single bit-set.
-template <class RelTy> static RelType getMipsN32RelType(RelTy *&rel, RelTy *end) {
+template <class RelTy>
+RelType RelocationScanner::getMipsN32RelType(RelTy *&rel) const {
   RelType type = 0;
   uint64_t offset = rel->r_offset;
 
   int n = 0;
-  while (rel != end && rel->r_offset == offset)
+  while (rel != static_cast<const RelTy *>(end) && rel->r_offset == offset)
     type |= (rel++)->getType(config->isMips64EL) << (8 * n++);
   return type;
 }
 
 static void addRelativeReloc(InputSectionBase &isec, uint64_t offsetInSec,
                              Symbol &sym, int64_t addend, RelExpr expr,
                              RelType type) {
   Partition &part = isec.getPartition();

 //
 // For instance, we know the offset from a relocation to its target at
 // link-time if the relocation is PC-relative and refers a
 // non-interposable function in the same executable. This function
 // will return true for such relocation.
 //
 // If this function returns false, that means we need to emit a
 // dynamic relocation so that the relocation will be fixed at load-time.
-static bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym,
-                                     InputSectionBase &s, uint64_t relOff) {
+bool RelocationScanner::isStaticLinkTimeConstant(RelExpr e, RelType type,
+                                                 const Symbol &sym,
+                                                 uint64_t relOff) const {
   // These expressions always compute a constant
   if (oneof<R_GOTPLT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL,
             R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC,
             R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC,
             R_PLT_PC, R_PLT_GOTPLT, R_PPC32_PLTREL, R_PPC64_CALL_PLT,
             R_PPC64_RELAX_TOC, R_RISCV_ADD, R_AARCH64_GOT_PAGE>(e))
     return true;
 
   // These never do, except if the entire file is position dependent or if
   // only the low bits are used.
   if (e == R_GOT || e == R_PLT)
-    return target->usesOnlyLowPageBits(type) || !config->isPic;
+    return target.usesOnlyLowPageBits(type) || !config->isPic;
 
   if (sym.isPreemptible)
     return false;
   if (!config->isPic)
     return true;
 
   // The size of a non preemptible symbol is a constant.
   if (e == R_SIZE)
     return true;
 
   // For the target and the relocation, we want to know if they are
   // absolute or relative.
   bool absVal = isAbsoluteValue(sym);
   bool relE = isRelExpr(e);
   if (absVal && !relE)
     return true;
   if (!absVal && relE)
     return true;
   if (!absVal && !relE)
-    return target->usesOnlyLowPageBits(type);
+    return target.usesOnlyLowPageBits(type);
 
   assert(absVal && relE);
 
   // Allow R_PLT_PC (optimized to R_PC here) to a hidden undefined weak symbol
   // in PIC mode. This is a little strange, but it allows us to link function
   // calls to such symbols (e.g. glibc/stdlib/exit.c:__run_exit_handlers).
   // Normally such a call will be guarded with a comparison, which will load a
   // zero from the GOT.
   if (sym.isUndefWeak())
     return true;
 
   // We set the final symbols values for linker script defined symbols later.
   // They always can be computed as a link time constant.
   if (sym.scriptDefined)
       return true;
 
   error("relocation " + toString(type) + " cannot refer to absolute symbol: " +
-        toString(sym) + getLocation(s, sym, relOff));
+        toString(sym) + getLocation(sec, sym, relOff));
   return true;
 }
 
 // The reason we have to do this early scan is as follows
 // * To mmap the output file, we need to know the size
 // * For that, we need to know how many dynamic relocs we will have.
 // It might be possible to avoid this by outputting the file with write:
 // * Write the allocated output sections, computing addresses.
 // * Apply relocations, recording which ones require a dynamic reloc.
 // * Write the dynamic relocations.
 // * Write the rest of the file.
 // This would have some drawbacks. For example, we would only know if .rela.dyn
 // is needed after applying relocations. If it is, it will go after rw and rx
 // sections. Given that it is ro, we will need an extra PT_LOAD. This
 // complicates things for the dynamic linker and means we would have to reserve
 // space for the extra PT_LOAD even if we end up not using it.
-template <class ELFT>
-static void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type,
-                            uint64_t offset, Symbol &sym, int64_t addend) {
+void RelocationScanner::processAux(RelExpr expr, RelType type, uint64_t offset,
+                                   Symbol &sym, int64_t addend) const {
   // If the relocation is known to be a link-time constant, we know no dynamic
   // relocation will be created, pass the control to relocateAlloc() or
   // relocateNonAlloc() to resolve it.
   //
   // The behavior of an undefined weak reference is implementation defined. For
   // non-link-time constants, we resolve relocations statically (let
   // relocate{,Non}Alloc() resolve them) for -no-pie and try producing dynamic
   // relocations for -pie and -shared.
   //
   // The general expectation of -no-pie static linking is that there is no
   // dynamic relocation (except IRELATIVE). Emitting dynamic relocations for
   // -shared matches the spirit of its -z undefs default. -pie has freedom on
   // choices, and we choose dynamic relocations to be consistent with the
   // handling of GOT-generating relocations.
-  if (isStaticLinkTimeConstant(expr, type, sym, sec, offset) ||
+  if (isStaticLinkTimeConstant(expr, type, sym, offset) ||
       (!config->isPic && sym.isUndefWeak())) {
     sec.relocations.push_back({expr, type, offset, addend, &sym});
     return;
   }
 
   bool canWrite = (sec.flags & SHF_WRITE) || !config->zText;
   if (canWrite) {
-    RelType rel = target->getDynRel(type);
-    if (expr == R_GOT || (rel == target->symbolicRel && !sym.isPreemptible)) {
+    RelType rel = target.getDynRel(type);
+    if (expr == R_GOT || (rel == target.symbolicRel && !sym.isPreemptible)) {
       addRelativeReloc(sec, offset, sym, addend, expr, type);
       return;
     } else if (rel != 0) {
-      if (config->emachine == EM_MIPS && rel == target->symbolicRel)
-        rel = target->relativeRel;
+      if (config->emachine == EM_MIPS && rel == target.symbolicRel)
+        rel = target.relativeRel;
       sec.getPartition().relaDyn->addSymbolReloc(rel, sec, offset, sym, addend,
                                                  type);
 
       // MIPS ABI turns using of GOT and dynamic relocations inside out.
       // While regular ABI uses dynamic relocations to fill up GOT entries
       // MIPS ABI requires dynamic linker to fills up GOT entries using
       // specially sorted dynamic symbol table. This affects even dynamic
       // relocations against symbols which do not require GOT entries
if (toExecRelax && isLocalInExecutable) {
         c.relocations.push_back({expr, type, offset, addend, &sym});
     }
     return 1;
   }
 
   return 0;
 }
 
-template <class ELFT, class RelTy>
-static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
-                      RelTy *end) {
+template <class ELFT, class RelTy> void RelocationScanner::scanOne(RelTy *&i) {
   const RelTy &rel = *i;
   uint32_t symIndex = rel.getSymbol(config->isMips64EL);
   Symbol &sym = sec.getFile<ELFT>()->getSymbol(symIndex);
   RelType type;
 
   // Deal with MIPS oddity.
   if (config->mipsN32Abi) {
-    type = getMipsN32RelType(i, end);
+    type = getMipsN32RelType(i);
   } else {
     type = rel.getType(config->isMips64EL);
     ++i;
   }
 
   // Get an offset in an output section this relocation is applied to.
-  uint64_t offset = getOffset.get(rel.r_offset);
+  uint64_t offset = getter.get(rel.r_offset);
   if (offset == uint64_t(-1))
     return;
 
   // Error if the target symbol is undefined. Symbol index 0 may be used by
   // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them.
   if (sym.isUndefined() && symIndex != 0 &&
       maybeReportUndefined(sym, sec, rel.r_offset))
     return;
 
   const uint8_t *relocatedAddr = sec.data().begin() + rel.r_offset;
-  RelExpr expr = target->getRelExpr(type, sym, relocatedAddr);
+  RelExpr expr = target.getRelExpr(type, sym, relocatedAddr);
 
   // Ignore R_*_NONE and other marker relocations.
   if (expr == R_NONE)
     return;
 
   // Read an addend.
-  int64_t addend = computeAddend<ELFT>(rel, end, sec, expr, sym.isLocal());
+  int64_t addend = computeAddend<ELFT>(rel, expr, sym.isLocal());
 
   if (config->emachine == EM_PPC64) {
     // We can separate the small code model relocations into 2 categories:
     // 1) Those that access the compiler generated .toc sections.
     // 2) Those that access the linker allocated got entries.
     // lld allocates got entries to symbols on demand. Since we don't try to
     // sort the got entries in any way, we don't have to track which objects
     // have got-based small code model relocs. The .toc sections get placed
if (oneof<R_GOTPLTONLY_PC, R_GOTPLTREL, R_GOTPLT, R_PLT_GOTPLT,
             R_TLSDESC_GOTPLT, R_TLSGD_GOTPLT>(expr)) {
     in.gotPlt->hasGotPltOffRel = true;
   } else if (oneof<R_GOTONLY_PC, R_GOTREL, R_PPC32_PLTREL, R_PPC64_TOCBASE,
                    R_PPC64_RELAX_TOC>(expr)) {
     in.got->hasGotOffRel = true;
   }
 
   // Process TLS relocations, including relaxing TLS relocations. Note that
-  // R_TPREL and R_TPREL_NEG relocations are resolved in processRelocAux.
+  // R_TPREL and R_TPREL_NEG relocations are resolved in processAux.
   if (expr == R_TPREL || expr == R_TPREL_NEG) {
     if (config->shared) {
       errorOrWarn("relocation " + toString(type) + " against " + toString(sym) +
                   " cannot be used with -shared" +
                   getLocation(sec, sym, offset));
       return;
     }
   } else if (unsigned processed =
if (expr != R_GOT_PC) {
       // R_HEX_GD_PLT_B22_PCREL (call a@GDPLT) is transformed into
       // call __tls_get_addr even if the symbol is non-preemptible.
       if (!(config->emachine == EM_HEXAGON &&
            (type == R_HEX_GD_PLT_B22_PCREL ||
             type == R_HEX_GD_PLT_B22_PCREL_X ||
             type == R_HEX_GD_PLT_B32_PCREL_X)))
       expr = fromPlt(expr);
     } else if (!isAbsoluteValue(sym)) {
-      expr = target->adjustGotPcExpr(type, addend, relocatedAddr);
+      expr = target.adjustGotPcExpr(type, addend, relocatedAddr);
     }
   }
 
   // We were asked not to generate PLT entries for ifuncs. Instead, pass the
   // direct relocation on through.
   if (sym.isGnuIFunc() && config->zIfuncNoplt) {
     sym.exportDynamic = true;
     mainPart->relaDyn->addSymbolReloc(type, sec, offset, sym, addend, type);
if (config->emachine == EM_MIPS) {
       sym.needsGot = true;
     }
   } else if (needsPlt(expr)) {
     sym.needsPlt = true;
   } else {
     sym.hasDirectReloc = true;
   }
 
-  processRelocAux<ELFT>(sec, expr, type, offset, sym, addend);
+  processAux(expr, type, offset, sym, addend);
 }
 
 // R_PPC64_TLSGD/R_PPC64_TLSLD is required to mark `bl __tls_get_addr` for
 // General Dynamic/Local Dynamic code sequences. If a GD/LD GOT relocation is
 // found but no R_PPC64_TLSGD/R_PPC64_TLSLD is seen, we assume that the
 // instructions are generated by very old IBM XL compilers. Work around the
 // issue by disabling GD/LD to IE/LE relaxation.
 template <class RelTy>
if (hasGDLD) {
     sec.file->ppc64DisableTLSRelax = true;
     warn(toString(sec.file) +
          ": disable TLS relaxation due to R_PPC64_GOT_TLS* relocations without "
          "R_PPC64_TLSGD/R_PPC64_TLSLD relocations");
   }
 }
 
 template <class ELFT, class RelTy>
-static void scanRelocs(InputSectionBase &sec, ArrayRef<RelTy> rels) {
-  OffsetGetter getOffset(sec);
-
+void RelocationScanner::scan(ArrayRef<RelTy> rels) {
   // Not all relocations end up in Sec.Relocations, but a lot do.
   sec.relocations.reserve(rels.size());
 
   if (config->emachine == EM_PPC64)
     checkPPC64TLSRelax<RelTy>(sec, rels);
 
   // For EhInputSection, OffsetGetter expects the relocations to be sorted by
   // r_offset. In rare cases (.eh_frame pieces are reordered by a linker
   // script), the relocations may be unordered.
   SmallVector<RelTy, 0> storage;
   if (isa<EhInputSection>(sec))
     rels = sortRels(rels, storage);
 
-  for (auto i = rels.begin(), end = rels.end(); i != end;)
-    scanReloc<ELFT>(sec, getOffset, i, end);
+  end = static_cast<const void *>(rels.end());
+  for (auto i = rels.begin(); i != end;)
+    scanOne<ELFT>(i);
 
   // Sort relocations by offset for more efficient searching for
   // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64.
   if (config->emachine == EM_RISCV ||
       (config->emachine == EM_PPC64 && sec.name == ".toc"))
     llvm::stable_sort(sec.relocations,
                       [](const Relocation &lhs, const Relocation &rhs) {
                         return lhs.offset < rhs.offset;
                       });
 }
 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &s) {
+  RelocationScanner scanner(s);
   const RelsOrRelas<ELFT> rels = s.template relsOrRelas<ELFT>();
   if (rels.areRelocsRel())
-    scanRelocs<ELFT>(s, rels.rels);
+    scanner.template scan<ELFT>(rels.rels);
   else
-    scanRelocs<ELFT>(s, rels.relas);
+    scanner.template scan<ELFT>(rels.relas);
 }
 
 static bool handleNonPreemptibleIfunc(Symbol &sym) {
   // Handle a reference to a non-preemptible ifunc. These are special in a
   // few ways:
   //
   // - Unlike most non-preemptible symbols, non-preemptible ifuncs do not have
   //   a fixed value. But assuming that all references to the ifunc are