[lld/ELF] Add flag to print relocation stats

[aeubanks]

Summary

This is useful for measuring relocation pressure across builds.

For now, print the min/max 32-bit signed offset across relocations.

[MaskRay]

This adds overhead to most relocations. The maximum offset doesn't necessarily reflect the pressure. We need to look at the distribution.
I am therefore object to such an approach.
As an alternative, we can relink with --emit-relocs and use another program to analyze the relocations.

[aeubanks]

In D158194#4595844, @MaskRay wrote:

This adds overhead to most relocations. The maximum offset doesn't necessarily reflect the pressure. We need to look at the distribution.
I am therefore object to such an approach.
As an alternative, we can relink with --emit-relocs and use another program to analyze the relocations.

I measured this (probably should have gotten numbers before sending this out) and yeah this does noticeably increase link times even when it's turned off so this current approach won't work.

But for continual monitoring of relocation pressure across binaries in a large build system, it's quite convenient to do this in the linker rather than as a separate step. Are you against all approaches of doing this in lld during the link (under a flag that won't impact link times at all), or just approaches in lld that affect lld link times?

[MaskRay]

In D158194#4595920, @aeubanks wrote:

In D158194#4595844, @MaskRay wrote:

This adds overhead to most relocations. The maximum offset doesn't necessarily reflect the pressure. We need to look at the distribution.
I am therefore object to such an approach.
As an alternative, we can relink with --emit-relocs and use another program to analyze the relocations.

I measured this (probably should have gotten numbers before sending this out) and yeah this does noticeably increase link times even when it's turned off so this current approach won't work.

But for continual monitoring of relocation pressure across binaries in a large build system, it's quite convenient to do this in the linker rather than as a separate step. Are you against all approaches of doing this in lld during the link (under a flag that won't impact link times at all), or just approaches in lld that affect lld link times?

I am concerned with any changes that affect the performance. Some really high-profile features can outweigh the cost, e.g. relocation overflow checking (the code your patch is changing), RISC-V linker relaxation.
For relocation monitoring, let me just be clearer. I think doing it in lld is almost always unacceptable. This is a data analysis task that should be done by another program.
Just use --emit-relocs.

[MaskRay]

I am generally concerned with any changes touching relocation scanning (including this and D142880). Last time I checked, lld's relocation scanning takes 2x time of mold's.

mold sections don't use struct Relocations. mold uses template class for all ports.

It's possible we should change our relocation scanning to be more mold like in the future.

[aeubanks]

while being able to measure relocation pressure across all binaries in our build system is nice, I'll look into monitoring specific binaries with a separate build that uses --emit-relocs and your relocation scanning binary that you wrote

lld/ELF/Config.h

struct Config {
   llvm::StringRef outputFile;
   llvm::StringRef optRemarksFilename;
   std::optional<uint64_t> optRemarksHotnessThreshold = 0;
   llvm::StringRef optRemarksPasses;
   llvm::StringRef optRemarksFormat;
   llvm::StringRef optStatsFilename;
   llvm::StringRef progName;
   llvm::StringRef printArchiveStats;
+  llvm::StringRef printRelocationStats;
   llvm::StringRef printSymbolOrder;
   llvm::StringRef soName;
   llvm::StringRef sysroot;
   llvm::StringRef thinLTOCacheDir;
   llvm::StringRef thinLTOIndexOnlyArg;
   llvm::StringRef whyExtract;
   llvm::StringRef cmseInputLib;
   llvm::StringRef cmseOutputLib;

lld/ELF/Driver.cpp

static void readConfigs(opt::InputArgList &args) {
   config->packageMetadata = args.getLastArgValue(OPT_package_metadata);
   config->pie = args.hasFlag(OPT_pie, OPT_no_pie, false);
   config->printIcfSections =
       args.hasFlag(OPT_print_icf_sections, OPT_no_print_icf_sections, false);
   config->printGcSections =
       args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
   config->printMemoryUsage = args.hasArg(OPT_print_memory_usage);
   config->printArchiveStats = args.getLastArgValue(OPT_print_archive_stats);
+  config->printRelocationStats =
+      args.getLastArgValue(OPT_print_relocation_stats);
   config->printSymbolOrder =
       args.getLastArgValue(OPT_print_symbol_order);
   config->relax = args.hasFlag(OPT_relax, OPT_no_relax, true);
   config->relaxGP = args.hasFlag(OPT_relax_gp, OPT_no_relax_gp, false);
   config->rpath = getRpath(args);
   config->relocatable = args.hasArg(OPT_relocatable);
 
   if (args.hasArg(OPT_save_temps)) {

lld/ELF/Options.td

 defm print_icf_sections: B<"print-icf-sections",
     "List identical folded sections",
     "Do not list identical folded sections (default)">;
 
 def print_archive_stats: J<"print-archive-stats=">,
   HelpText<"Write archive usage statistics to the specified file. "
            "Print the numbers of members and extracted members for each archive">;
 
+defm print_relocation_stats: Eq<"print-relocation-stats",
+  "Print relocation statistics into the specified file">;
+
 defm print_symbol_order: Eq<"print-symbol-order",
   "Print a symbol order specified by --call-graph-ordering-file into the specified file">;
 
 def pop_state: F<"pop-state">,
   HelpText<"Restore the states saved by --push-state">;
 
 def push_state: F<"push-state">,
   HelpText<"Save the current state of --as-needed, -static and --whole-archive">;

lld/ELF/Target.h

 
 template <class ELFT> bool isMipsPIC(const Defined *sym);
 
 void reportRangeError(uint8_t *loc, const Relocation &rel, const Twine &v,
                       int64_t min, uint64_t max);
 void reportRangeError(uint8_t *loc, int64_t v, int n, const Symbol &sym,
                       const Twine &msg);
 
+LLVM_LIBRARY_VISIBILITY inline std::atomic<int64_t> min32Offset = 0,
+                                                    max32Offset = 0;
+LLVM_LIBRARY_VISIBILITY inline std::mutex min32OffsetMu, max32OffsetMu;
+
 // Make sure that V can be represented as an N bit signed integer.
 inline void checkInt(uint8_t *loc, int64_t v, int n, const Relocation &rel) {
   if (v != llvm::SignExtend64(v, n))
     reportRangeError(loc, rel, Twine(v), llvm::minIntN(n), llvm::maxIntN(n));
+  // If we request relocation stats, perform double checked locking to keep
+  // track of the min/max 32-bit signed offset we encounter.
+  if (n == 32 && !config->printRelocationStats.empty()) {
+    int64_t lo = min32Offset.load();
+    if (v < lo) {
+      std::lock_guard<std::mutex> l(min32OffsetMu);
+      if (v < min32Offset)
+        min32Offset = v;
+    }
+    int64_t hi = max32Offset.load();
+    if (v > hi) {
+      std::lock_guard<std::mutex> l(max32OffsetMu);
+      if (v > max32Offset)
+        max32Offset = v;
+    }
+  }
 }
 
 // Make sure that V can be represented as an N bit unsigned integer.
 inline void checkUInt(uint8_t *loc, uint64_t v, int n, const Relocation &rel) {
   if ((v >> n) != 0)
     reportRangeError(loc, rel, Twine(v), 0, llvm::maxUIntN(n));
 }
 

lld/ELF/Writer.cpp

 #include "lld/Common/CommonLinkerContext.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Strings.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/BLAKE3.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/TimeProfiler.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/xxhash.h"
 #include <climits>
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
private:
   void checkSections();
   void fixSectionAlignments();
   void openFile();
   void writeTrapInstr();
   void writeHeader();
   void writeSections();
   void writeSectionsBinary();
   void writeBuildId();
+  void writeStats();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
 
   void addRelIpltSymbols();
   void addStartEndSymbols();
   void addStartStopSymbols(OutputSection &osec);
 
   uint64_t fileSize;
if (!config->oFormatBinary) {
       writeSections();
     } else {
       writeSectionsBinary();
     }
 
     // Backfill .note.gnu.build-id section content. This is done at last
     // because the content is usually a hash value of the entire output file.
     writeBuildId();
+    writeStats();
     if (errorCount())
       return;
 
     if (auto e = buffer->commit())
       fatal("failed to write output '" + buffer->getPath() +
             "': " + toString(std::move(e)));
 
     if (!config->cmseOutputLib.empty())
case BuildIdKind::Uuid:
     break;
   default:
     llvm_unreachable("unknown BuildIdKind");
   }
   for (Partition &part : partitions)
     part.buildId->writeBuildId(output);
 }
 
+template <class ELFT> void Writer<ELFT>::writeStats() {
+  if (config->printRelocationStats.empty())
+    return;
+  std::error_code ec;
+  llvm::raw_fd_ostream out(config->printRelocationStats, ec);
+  if (ec) {
+    error("Could not open file to write stats: " + ec.message());
+    return;
+  }
+  out << "Min 32-bit offset: " << min32Offset << "\n";
+  out << "Max 32-bit offset: " << max32Offset << "\n";
+}
+
 template void elf::createSyntheticSections<ELF32LE>();
 template void elf::createSyntheticSections<ELF32BE>();
 template void elf::createSyntheticSections<ELF64LE>();
 template void elf::createSyntheticSections<ELF64BE>();
 
 template void elf::writeResult<ELF32LE>();
 template void elf::writeResult<ELF32BE>();
 template void elf::writeResult<ELF64LE>();
 template void elf::writeResult<ELF64BE>();

lld/test/ELF/print-relocation-stats.s

+# REQUIRES: x86
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/a.s -o %t/a.o
+# RUN: ld.lld -T %t/lds %t/a.o -o /dev/null --print-relocation-stats=%t/stats
+# RUN: FileCheck %s --input-file %t/stats
+
+# CHECK: Min 32-bit offset: -99999
+# CHECK: Max 32-bit offset: 199994
+
+#--- a.s
+.section data1,"aw",@progbits
+.space 8
+
+.section .text, "ax", @progbits
+  movq __stop_data1@GOTPCREL(%rip), %rax
+  movq __stop_data2@GOTPCREL(%rip), %rax
+
+.section data2,"aw",@progbits
+.space 8
+
+#--- lds
+SECTIONS {
+  data1 100000 : { *(data1) }
+  .text 200000 : { *(.text) }
+  data2 400000 : { *(data2) }
+}
+