[lld-macho] Devirtualize TargetInfo::getRelocAttrs

[BertalanD]

Summary

This method is called on each relocation when parsing input files, so
the overhead of using virtual functions ends up being quite large. We
now have a single non-virtual method, which reads from the appropriate
array of relocation attributes set in the TargetInfo's constructor.

This change results in a modest 2.7% reduction in link time for
chromium_framework measured on my GCP instance:

x before
+ after
+---------------------------------------------------------------------+
|                          +                                          |
|     +   +   +            +             x      xx                    |
|+   +++ ++ + +++++ +     ++         x xxx    xxxxxx x xxx   x   x   x|
|     |_______A_______|                  |_______MA________|          |
+---------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  20     11.992883     12.289202     12.107467     12.114866   0.079527048
+  20     11.662653     11.903168     11.785559     11.785649   0.073029551
Difference at 95.0% confidence
	-0.329216 +/- 0.0488658
	-2.71746% +/- 0.403354%
	(Student's t, pooled s = 0.0763475)

[int3]

Nice! 2.7% is not modest :)

[thakis]

Nice!

Slightly smaller win over here on my mbp:

% ministat ~/lld-arm-pre.txt ~/lld-arm-post.txt
x /Users/thakis/lld-arm-pre.txt
+ /Users/thakis/lld-arm-post.txt
+-------------------------------------------------------------------------------------+
|+ +             +   + x  ++    x+         *  x    *+     x           x x            x|
|         |________________A_|_______________|____AM___________________|              |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  10     3.9939671       4.07289      4.029876     4.0286749   0.026863766
+  10      3.965914     4.0304928     3.9992213     3.9994131    0.02260193
Difference at 95.0% confidence
	-0.0292618 +/- 0.023325
	-0.726338% +/- 0.578974%
	(Student's t, pooled s = 0.0248245)

[BertalanD]

I did fudge up the test because I accidentally included an unrelated change. Here are the accurate numbers, still on GCE:

Difference at 95.0% confidence
    -0.181568 +/- 0.0814132
    -2.00135% +/- 0.897384%
    (Student's t, pooled s = 0.0866471)

lld/MachO/Arch/ARM.cpp

void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t pc) const override;
 
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
 
   void relaxGotLoad(uint8_t *loc, uint8_t type) const override;
-  const RelocAttrs &getRelocAttrs(uint8_t type) const override;
   uint64_t getPageSize() const override { return 4 * 1024; }
 
   void handleDtraceReloc(const Symbol *sym, const Reloc &r,
                          uint8_t *loc) const override;
 };
-
 } // namespace
 
-const RelocAttrs &ARM::getRelocAttrs(uint8_t type) const {
-  static const std::array<RelocAttrs, 10> relocAttrsArray{{
+static constexpr std::array<RelocAttrs, 10> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
-      {"VANILLA", /* FIXME populate this */ B(_0)},
-      {"PAIR", /* FIXME populate this */ B(_0)},
-      {"SECTDIFF", /* FIXME populate this */ B(_0)},
-      {"LOCAL_SECTDIFF", /* FIXME populate this */ B(_0)},
-      {"PB_LA_PTR", /* FIXME populate this */ B(_0)},
-      {"BR24", B(PCREL) | B(LOCAL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
-      {"BR22", B(PCREL) | B(LOCAL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
-      {"32BIT_BRANCH", /* FIXME populate this */ B(_0)},
-      {"HALF", /* FIXME populate this */ B(_0)},
-      {"HALF_SECTDIFF", /* FIXME populate this */ B(_0)},
 #undef B
-  }};
-  assert(type < relocAttrsArray.size() && "invalid relocation type");
-  if (type >= relocAttrsArray.size())
-    return invalidRelocAttrs;
-  return relocAttrsArray[type];
-}
 
 int64_t ARM::getEmbeddedAddend(MemoryBufferRef mb, uint64_t offset,
                                relocation_info rel) const {
   // FIXME: implement this
   return 0;
 }
 
 template <int N> using BitfieldFlag = Bitfield::Element<bool, N, 1>;

 
 ARM::ARM(uint32_t cpuSubtype) : TargetInfo(ILP32()) {
   cpuType = CPU_TYPE_ARM;
   this->cpuSubtype = cpuSubtype;
 
   stubSize = 0 /* FIXME */;
   stubHelperHeaderSize = 0 /* FIXME */;
   stubHelperEntrySize = 0 /* FIXME */;
+
+  relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
 }
 
 TargetInfo *macho::createARMTargetInfo(uint32_t cpuSubtype) {
   static ARM t(cpuSubtype);
   return &t;
 }
 
 void ARM::handleDtraceReloc(const Symbol *sym, const Reloc &r,

lld/MachO/Arch/ARM64.cpp

 namespace {
 
 struct ARM64 : ARM64Common {
   ARM64();
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
-  const RelocAttrs &getRelocAttrs(uint8_t type) const override;
   void populateThunk(InputSection *thunk, Symbol *funcSym) override;
   void applyOptimizationHints(uint8_t *, const ConcatInputSection *,
                               ArrayRef<uint64_t>) const override;
 };
 
 } // namespace
 
 // Random notes on reloc types:
 // ADDEND always pairs with BRANCH26, PAGE21, or PAGEOFF12
 // POINTER_TO_GOT: ld64 supports a 4-byte pc-relative form as well as an 8-byte
 // absolute version of this relocation. The semantics of the absolute relocation
 // are weird -- it results in the value of the GOT slot being written, instead
 // of the address. Let's not support it unless we find a real-world use case.
-
-const RelocAttrs &ARM64::getRelocAttrs(uint8_t type) const {
-  static const std::array<RelocAttrs, 11> relocAttrsArray{{
+static constexpr std::array<RelocAttrs, 11> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
-      {"UNSIGNED",
-       B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
-      {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
-      {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
-      {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
-      {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
-      {"GOT_LOAD_PAGEOFF12",
-       B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
-      {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
-      {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},
-      {"TLVP_LOAD_PAGEOFF12",
-       B(ABSOLUTE) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
-      {"ADDEND", B(ADDEND)},
 #undef B
-  }};
-  assert(type < relocAttrsArray.size() && "invalid relocation type");
-  if (type >= relocAttrsArray.size())
-    return invalidRelocAttrs;
-  return relocAttrsArray[type];
-}
 
 static constexpr uint32_t stubCode[] = {
     0x90000010, // 00: adrp  x16, __la_symbol_ptr@page
     0xf9400210, // 04: ldr   x16, [x16, __la_symbol_ptr@pageoff]
     0xd61f0200, // 08: br    x16
 };
 
 void ARM64::writeStub(uint8_t *buf8, const Symbol &sym) const {
ARM64::ARM64() : ARM64Common(LP64()) {
   forwardBranchRange = backwardBranchRange - 4;
 
   modeDwarfEncoding = UNWIND_ARM64_MODE_DWARF;
   subtractorRelocType = ARM64_RELOC_SUBTRACTOR;
   unsignedRelocType = ARM64_RELOC_UNSIGNED;
 
   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
   stubHelperEntrySize = sizeof(stubHelperEntryCode);
+
+  relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
 }
 
 namespace {
 struct Adrp {
   uint32_t destRegister;
 };
 
 struct Add {

lld/MachO/Arch/ARM64_32.cpp

 namespace {
 
 struct ARM64_32 : ARM64Common {
   ARM64_32();
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
-  const RelocAttrs &getRelocAttrs(uint8_t type) const override;
 };
 
 } // namespace
 
 // These are very similar to ARM64's relocation attributes, except that we don't
 // have the BYTE8 flag set.
-const RelocAttrs &ARM64_32::getRelocAttrs(uint8_t type) const {
-  static const std::array<RelocAttrs, 11> relocAttrsArray{{
+static constexpr std::array<RelocAttrs, 11> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
-      {"UNSIGNED", B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4)},
-      {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
-      {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
-      {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
-      {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
-      {"GOT_LOAD_PAGEOFF12",
-       B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
-      {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
-      {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},
-      {"TLVP_LOAD_PAGEOFF12",
-       B(ABSOLUTE) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
-      {"ADDEND", B(ADDEND)},
 #undef B
-  }};
-  assert(type < relocAttrsArray.size() && "invalid relocation type");
-  if (type >= relocAttrsArray.size())
-    return invalidRelocAttrs;
-  return relocAttrsArray[type];
-}
 
 // The stub code is fairly similar to ARM64's, except that we load pointers into
 // 32-bit 'w' registers, instead of the 64-bit 'x' ones.
 
 static constexpr uint32_t stubCode[] = {
     0x90000010, // 00: adrp  x16, __la_symbol_ptr@page
     0xb9400210, // 04: ldr   w16, [x16, __la_symbol_ptr@pageoff]
     0xd61f0200, // 08: br    x16
ARM64_32::ARM64_32() : ARM64Common(ILP32()) {
 
   modeDwarfEncoding = 0x04000000;              // UNWIND_ARM_MODE_DWARF
   subtractorRelocType = GENERIC_RELOC_INVALID; // FIXME
   unsignedRelocType = GENERIC_RELOC_INVALID;   // FIXME
 
   stubSize = sizeof(stubCode);
   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
   stubHelperEntrySize = sizeof(stubHelperEntryCode);
+
+  relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
 }
 
 TargetInfo *macho::createARM64_32TargetInfo() {
   static ARM64_32 t;
   return &t;
 }

lld/MachO/Arch/X86_64.cpp

void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t relocVA) const override;
 
   void writeStub(uint8_t *buf, const Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
                             uint64_t entryAddr) const override;
 
   void relaxGotLoad(uint8_t *loc, uint8_t type) const override;
-  const RelocAttrs &getRelocAttrs(uint8_t type) const override;
   uint64_t getPageSize() const override { return 4 * 1024; }
 
   void handleDtraceReloc(const Symbol *sym, const Reloc &r,
                          uint8_t *loc) const override;
 };
-
 } // namespace
 
-const RelocAttrs &X86_64::getRelocAttrs(uint8_t type) const {
-  static const std::array<RelocAttrs, 10> relocAttrsArray{{
+static constexpr std::array<RelocAttrs, 10> relocAttrsArray{{
 #define B(x) RelocAttrBits::x
-      {"UNSIGNED",
-       B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
-      {"SIGNED", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
-      {"BRANCH", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
-      {"GOT_LOAD", B(PCREL) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
-      {"GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
-      {"SIGNED_1", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
-      {"SIGNED_2", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
-      {"SIGNED_4", B(PCREL) | B(EXTERN) | B(LOCAL) | B(BYTE4)},
-      {"TLV", B(PCREL) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
 #undef B
-  }};
-  assert(type < relocAttrsArray.size() && "invalid relocation type");
-  if (type >= relocAttrsArray.size())
-    return invalidRelocAttrs;
-  return relocAttrsArray[type];
-}
 
 static int pcrelOffset(uint8_t type) {
   switch (type) {
   case X86_64_RELOC_SIGNED_1:
     return 1;
   case X86_64_RELOC_SIGNED_2:
     return 2;
   case X86_64_RELOC_SIGNED_4:
X86_64::X86_64() : TargetInfo(LP64()) {
 
   modeDwarfEncoding = UNWIND_X86_MODE_DWARF;
   subtractorRelocType = X86_64_RELOC_SUBTRACTOR;
   unsignedRelocType = X86_64_RELOC_UNSIGNED;
 
   stubSize = sizeof(stub);
   stubHelperHeaderSize = sizeof(stubHelperHeader);
   stubHelperEntrySize = sizeof(stubHelperEntry);
+
+  relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
 }
 
 TargetInfo *macho::createX86_64TargetInfo() {
   static X86_64 t;
   return &t;
 }
 
 void X86_64::handleDtraceReloc(const Symbol *sym, const Reloc &r,

lld/MachO/Target.h

public:
 
   // Symbols may be referenced via either the GOT or the stubs section,
   // depending on the relocation type. prepareSymbolRelocation() will set up the
   // GOT/stubs entries, and resolveSymbolVA() will return the addresses of those
   // entries. resolveSymbolVA() may also relax the target instructions to save
   // on a level of address indirection.
   virtual void relaxGotLoad(uint8_t *loc, uint8_t type) const = 0;
 
-  virtual const RelocAttrs &getRelocAttrs(uint8_t type) const = 0;
-
   virtual uint64_t getPageSize() const = 0;
 
   virtual void populateThunk(InputSection *thunk, Symbol *funcSym) {
     llvm_unreachable("target does not use thunks");
   }
 
+  const RelocAttrs &getRelocAttrs(uint8_t type) const {
+    assert(type < relocAttrs.size() && "invalid relocation type");
+    if (type >= relocAttrs.size())
+      return invalidRelocAttrs;
+    return relocAttrs[type];
+  }
+
   bool hasAttr(uint8_t type, RelocAttrBits bit) const {
     return getRelocAttrs(type).hasAttr(bit);
   }
 
   bool usesThunks() const { return thunkSize > 0; }
 
   // For now, handleDtraceReloc only implements -no_dtrace_dof, and ensures
   // that the linking would not fail even when there are user-provided dtrace
public:
   size_t thunkSize = 0;
   uint64_t forwardBranchRange = 0;
   uint64_t backwardBranchRange = 0;
 
   uint32_t modeDwarfEncoding;
   uint8_t subtractorRelocType;
   uint8_t unsignedRelocType;
 
+  llvm::ArrayRef<RelocAttrs> relocAttrs;
+
   // We contrive this value as sufficiently far from any valid address that it
   // will always be out-of-range for any architecture. UINT64_MAX is not a
   // good choice because it is (a) only 1 away from wrapping to 0, and (b) the
   // tombstone value for DenseMap<> and caused weird assertions for me.
   static constexpr uint64_t outOfRangeVA = 0xfull << 60;
 };
 
 TargetInfo *createX86_64TargetInfo();