[lld-macho] Optimize getRelocAttrs()

[int3]

Summary

Investigation of PR49480 showed that D95121 caused about a 5.0% speed
regression when linking chromium_framework. That diff introduces a (very
useful) additional layer of abstraction over relocations, so the perf
overhead is not too surprising. The diff is pretty large, and perf
didn't give me any great hints, so I just went with optimizing the
likely candidate -- getRelocAttrs(). I managed to claw back about
1.4% of perf this way. Making the relocAttrsArray a global and
devirtualizing getRelocAttrs() gave most of the win; I also marked
the array range check with LLVM_UNLIKELY for good measure.

The numbers above are quoted for chromium_framework (from the tarball in
PR48657).

    N           Min           Max        Median           Avg        Stddev
x  20           4.5          4.66          4.56        4.5715   0.044871161
+  20          4.42          4.61           4.5        4.5075   0.053001986
Difference at 95.0% confidence
        -0.064 +/- 0.0314295
        -1.39998% +/- 0.68751%
        (Student's t, pooled s = 0.0491052)

I also measured v8_unittests:

    N           Min           Max        Median           Avg        Stddev
x  20          0.62          0.65          0.64        0.6355  0.0082557795
+  20          0.61          0.63          0.62         0.616  0.0059824304
Difference at 95.0% confidence
        -0.0195 +/- 0.00461426
        -3.06845% +/- 0.726084%
        (Student's t, pooled s = 0.00720928)

The v8 difference is likely larger because it doesn't use an order file.
Symbol ordering is actually one of the most expensive steps when linking
chromium_framework, and probably is a target for further optimization.

The other hotspot is the assignment of relocations to subsections. I'm
curious as to whether replacing the RB-tree in std::map with a radix
trie would be an improvement...

[tschuett]

LLVM is not a big fan of std::map:
https://llvm.org/docs/ProgrammersManual.html#map

[int3]

I'm aware :) the reason why we're using it here is because we need upper_bound(). That said, a sorted vector (as mentioned in the manual) might help here... parseSymbols interleaves inserts and queries to the SubsectionMaps, but parseRelocations only does queries, so we could convert the map to a vector in the latter case.

[int3]

update

[int3]

maybe using templates would be better here, similar to LLD-ELF's ELFT type. Thanks @smeenai for the idea

[int3]

This is kind of ugly, and I think there's lower-hanging performance fruit, so we can revisit this later

lld/MachO/Arch/ARM64.cpp

void relocateOne(uint8_t *loc, const Reloc &, uint64_t va,
                    uint64_t pc) const override;
 
   void writeStub(uint8_t *buf, const macho::Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                             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 16 * 1024; }
 };
 
 } // 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 const std::array<RelocAttrs, 11> ARM64RelocAttrsArray{{
 #define B(x) RelocAttrBits::x
-      {"UNSIGNED", B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) |
-                       B(DYSYM8) | B(BYTE4) | B(BYTE8)},
-      {"SUBTRACTOR", B(SUBTRAHEND) | 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)},
+    {"UNSIGNED", B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(DYSYM8) |
+                     B(BYTE4) | B(BYTE8)},
 #undef B
-  }};
-  assert(type < relocAttrsArray.size() && "invalid relocation type");
-  if (type >= relocAttrsArray.size())
-    return invalidRelocAttrs;
-  return relocAttrsArray[type];
-}
 
 int64_t ARM64::getEmbeddedAddend(MemoryBufferRef mb, const section_64 &sec,
                                  const relocation_info rel) const {
   if (rel.r_type != ARM64_RELOC_UNSIGNED &&
       rel.r_type != ARM64_RELOC_SUBTRACTOR) {
     // All other reloc types should use the ADDEND relocation to store their
     // addends.
     // TODO(gkm): extract embedded addend just so we can assert that it is 0
ARM64::ARM64() {
 
   stubSize = sizeof(stubCode);
   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
   stubHelperEntrySize = sizeof(stubHelperEntryCode);
 }
 
 TargetInfo *macho::createARM64TargetInfo() {
   static ARM64 t;
+  relocAttrsArray = ARM64RelocAttrsArray.data();
+  relocAttrsArraySize = ARM64RelocAttrsArray.size();
   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 macho::Symbol &) const override;
   void writeStubHelperHeader(uint8_t *buf) const override;
   void writeStubHelperEntry(uint8_t *buf, const DylibSymbol &,
                             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; }
 };
 
 } // namespace
 
-const RelocAttrs &X86_64::getRelocAttrs(uint8_t type) const {
-  static const std::array<RelocAttrs, 10> relocAttrsArray{{
+static const std::array<RelocAttrs, 10> X86_64RelocAttrsArray{{
 #define B(x) RelocAttrBits::x
-      {"UNSIGNED", B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) |
-                       B(DYSYM8) | 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(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)},
+    {"UNSIGNED", B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(DYSYM8) |
+                     B(BYTE4) | B(BYTE8)},
 #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() {
 
   stubSize = sizeof(stub);
   stubHelperHeaderSize = sizeof(stubHelperHeader);
   stubHelperEntrySize = sizeof(stubHelperEntry);
 }
 
 TargetInfo *macho::createX86_64TargetInfo() {
   static X86_64 t;
+  relocAttrsArray = X86_64RelocAttrsArray.data();
+  relocAttrsArraySize = X86_64RelocAttrsArray.size();
   return &t;
 }

lld/MachO/InputFiles.cpp

static InputSection *findContainingSubsection(SubsectionMap &map,
                                               uint32_t *offset) {
   auto it = std::prev(map.upper_bound(*offset));
   *offset -= it->first;
   return it->second;
 }
 
 static bool validateRelocationInfo(InputFile *file, const section_64 &sec,
                                    relocation_info rel) {
-  const RelocAttrs &relocAttrs = target->getRelocAttrs(rel.r_type);
+  const RelocAttrs &relocAttrs = getRelocAttrs(rel.r_type);
   bool valid = true;
   auto message = [relocAttrs, file, sec, rel, &valid](const Twine &diagnostic) {
     valid = false;
     return (relocAttrs.name + " relocation " + diagnostic + " at offset " +
             std::to_string(rel.r_address) + " of " + sec.segname + "," +
             sec.sectname + " in " + toString(file))
         .str();
   };
for (size_t i = 0; i < relInfos.size(); i++) {
     // instruction-stream bytes that would otherwise contain zeroes. By
     // contrast, RISC ISAs such as ARM64 mix opcode bits with with
     // address bits so that bitwise arithmetic is necessary to extract
     // and insert them. Storing addends in the instruction stream is
     // possible, but inconvenient and more costly at link time.
 
     int64_t pairedAddend = 0;
     relocation_info relInfo = relInfos[i];
-    if (target->hasAttr(relInfo.r_type, RelocAttrBits::ADDEND)) {
+    if (hasRelocAttr(relInfo.r_type, RelocAttrBits::ADDEND)) {
       pairedAddend = SignExtend64<24>(relInfo.r_symbolnum);
       relInfo = relInfos[++i];
     }
     assert(i < relInfos.size());
     if (!validateRelocationInfo(this, sec, relInfo))
       continue;
     if (relInfo.r_address & R_SCATTERED)
       fatal("TODO: Scattered relocations not supported");
if (relInfo.r_extern) {
       uint32_t referentOffset;
       if (relInfo.r_pcrel) {
         // The implicit addend for pcrel section relocations is the pcrel offset
         // in terms of the addresses in the input file. Here we adjust it so
         // that it describes the offset from the start of the referent section.
         // FIXME This logic was written around x86_64 behavior -- ARM64 doesn't
         // have pcrel section relocations. We may want to factor this out into
         // the arch-specific .cpp file.
-        assert(target->hasAttr(r.type, RelocAttrBits::BYTE4));
+        assert(hasRelocAttr(r.type, RelocAttrBits::BYTE4));
         referentOffset =
             sec.addr + relInfo.r_address + 4 + totalAddend - referentSec.addr;
       } else {
         // The addend for a non-pcrel relocation is its absolute address.
         referentOffset = totalAddend - referentSec.addr;
       }
       r.referent = findContainingSubsection(referentSubsecMap, &referentOffset);
       r.addend = referentOffset;
     }
 
     InputSection *subsec = findContainingSubsection(subsecMap, &r.offset);
     subsec->relocs.push_back(r);
 
-    if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
+    if (hasRelocAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
       relInfo = relInfos[++i];
       // SUBTRACTOR relocations should always be followed by an UNSIGNED one
       // indicating the minuend symbol.
-      assert(target->hasAttr(relInfo.r_type, RelocAttrBits::UNSIGNED) &&
+      assert(hasRelocAttr(relInfo.r_type, RelocAttrBits::UNSIGNED) &&
              relInfo.r_extern);
       Reloc p;
       p.type = relInfo.r_type;
       p.referent = symbols[relInfo.r_symbolnum];
       subsec->relocs.push_back(p);
     }
   }
 }

lld/MachO/InputSection.cpp

 uint64_t InputSection::getFileSize() const {
   return isZeroFill(flags) ? 0 : getSize();
 }
 
 uint64_t InputSection::getVA() const { return parent->addr + outSecOff; }
 
 static uint64_t resolveSymbolVA(uint8_t *loc, const lld::macho::Symbol &sym,
                                 uint8_t type) {
-  const RelocAttrs &relocAttrs = target->getRelocAttrs(type);
+  const RelocAttrs &relocAttrs = getRelocAttrs(type);
   if (relocAttrs.hasAttr(RelocAttrBits::BRANCH)) {
     if (sym.isInStubs())
       return in.stubs->addr + sym.stubsIndex * target->stubSize;
   } else if (relocAttrs.hasAttr(RelocAttrBits::GOT)) {
     if (sym.isInGot())
       return in.got->addr + sym.gotIndex * WordSize;
   } else if (relocAttrs.hasAttr(RelocAttrBits::TLV)) {
     if (sym.isInGot())
       return in.tlvPointers->addr + sym.gotIndex * WordSize;
     assert(isa<Defined>(&sym));
   }
   return sym.getVA();
 }
 
 void InputSection::writeTo(uint8_t *buf) {
   if (getFileSize() == 0)
     return;
 
   memcpy(buf, data.data(), data.size());
 
   for (size_t i = 0; i < relocs.size(); i++) {
     const Reloc &r = relocs[i];
     uint8_t *loc = buf + r.offset;
     uint64_t referentVA = 0;
-    if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
+    if (hasRelocAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
       const Symbol *fromSym = r.referent.get<Symbol *>();
       const Symbol *toSym = relocs[++i].referent.get<Symbol *>();
       referentVA = toSym->getVA() - fromSym->getVA();
     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
-      if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
-          !referentSym->isInGot())
+      if (hasRelocAttr(r.type, RelocAttrBits::LOAD) && !referentSym->isInGot())
         target->relaxGotLoad(loc, r.type);
       referentVA = resolveSymbolVA(loc, *referentSym, r.type);
 
       if (isThreadLocalVariables(flags)) {
         // References from thread-local variable sections are treated as offsets
         // relative to the start of the thread-local data memory area, which
         // is initialized via copying all the TLV data sections (which are all
         // contiguous).

lld/MachO/Relocations.cpp

 #include "lld/Common/ErrorHandler.h"
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::macho;
 
 bool macho::validateSymbolRelocation(const Symbol *sym,
                                      const InputSection *isec, const Reloc &r) {
-  const RelocAttrs &relocAttrs = target->getRelocAttrs(r.type);
+  const RelocAttrs &relocAttrs = getRelocAttrs(r.type);
   bool valid = true;
   auto message = [relocAttrs, sym, isec, &valid](const Twine &diagnostic) {
     valid = false;
     return (relocAttrs.name + " relocation " + diagnostic + " for `" +
             sym->getName() + "' in " + toString(isec))
         .str();
   };
 

 }
 
 void macho::reportRangeError(const Reloc &r, const Twine &v, uint8_t bits,
                              int64_t min, uint64_t max) {
   std::string hint;
   if (auto *sym = r.referent.dyn_cast<Symbol *>())
     hint = "; references " + toString(*sym);
   // TODO: get location of reloc using something like LLD-ELF's getErrorPlace()
-  error("relocation " + target->getRelocAttrs(r.type).name +
-        " is out of range: " + v + " is not in [" + Twine(min) + ", " +
-        Twine(max) + "]" + hint);
+  error("relocation " + getRelocAttrs(r.type).name + " is out of range: " + v +
+        " is not in [" + Twine(min) + ", " + Twine(max) + "]" + hint);
 }
 
 void macho::reportRangeError(SymbolDiagnostic d, const Twine &v, uint8_t bits,
                              int64_t min, uint64_t max) {
   std::string hint;
   if (d.symbol)
     hint = "; references " + toString(*d.symbol);
   error(d.reason + " is out of range: " + v + " is not in [" + Twine(min) +
         ", " + Twine(max) + "]" + hint);
 }
 
 const RelocAttrs macho::invalidRelocAttrs{"INVALID", RelocAttrBits::_0};

lld/MachO/Target.h

 //===- Target.h -------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_TARGET_H
 #define LLD_MACHO_TARGET_H
 
 #include "Relocations.h"
 
 #include "llvm/ADT/BitmaskEnum.h"
 #include "llvm/BinaryFormat/MachO.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 #include <cstddef>
 #include <cstdint>
 
 namespace lld {
 namespace macho {
 LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE();
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;
 
-  bool hasAttr(uint8_t type, RelocAttrBits bit) const {
-    return getRelocAttrs(type).hasAttr(bit);
-  }
-
   bool validateRelocationInfo(llvm::MemoryBufferRef,
                               const llvm::MachO::section_64 &sec,
                               llvm::MachO::relocation_info);
   void prepareSymbolRelocation(Symbol *, const InputSection *, const Reloc &);
 
   uint32_t cpuType;
   uint32_t cpuSubtype;
 
   size_t stubSize;
   size_t stubHelperHeaderSize;
   size_t stubHelperEntrySize;
 };
 
 TargetInfo *createX86_64TargetInfo();
 TargetInfo *createARM64TargetInfo();
 
 extern TargetInfo *target;
 
+// These values are target-specific, but we have hoisted them out of Target
+// because they are accessed in hot loops. Avoiding the extra indirection is a
+// perf win.
+extern size_t relocAttrsArraySize;
+extern const RelocAttrs *relocAttrsArray;
+
+inline const RelocAttrs &getRelocAttrs(uint8_t type) {
+  if (LLVM_UNLIKELY(type >= relocAttrsArraySize))
+    return invalidRelocAttrs;
+  return relocAttrsArray[type];
+}
+
+inline bool hasRelocAttr(uint8_t type, RelocAttrBits bit) {
+  return getRelocAttrs(type).hasAttr(bit);
+}
+
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Target.cpp

 //===- Target.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Target.h"
 
 using namespace lld;
 using namespace lld::macho;
 
 TargetInfo *macho::target = nullptr;
+size_t macho::relocAttrsArraySize = 0;
+const RelocAttrs *macho::relocAttrsArray = nullptr;

lld/MachO/UnwindInfoSection.cpp

 // rebase opcodes for __LD,__compact_unwind, because that section doesn't
 // actually end up in the final binary. Second, personality pointers always
 // reside in the GOT and must be treated specially.
 void macho::prepareCompactUnwind(InputSection *isec) {
   assert(isec->segname == segment_names::ld &&
          isec->name == section_names::compactUnwind);
 
   for (Reloc &r : isec->relocs) {
-    assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED));
+    assert(hasRelocAttr(r.type, RelocAttrBits::UNSIGNED));
     if (r.offset % sizeof(CompactUnwindEntry64) !=
         offsetof(struct CompactUnwindEntry64, personality))
       continue;
 
     if (auto *s = r.referent.dyn_cast<lld::macho::Symbol *>()) {
       if (auto *undefined = dyn_cast<Undefined>(s)) {
         treatUndefinedSymbol(*undefined);
         // treatUndefinedSymbol() can replace s with a DylibSymbol; re-check.

lld/MachO/Writer.cpp

public:
 
   CodeSignatureSection *section;
 };
 
 } // namespace
 
 static void prepareSymbolRelocation(lld::macho::Symbol *sym,
                                     const InputSection *isec, const Reloc &r) {
-  const RelocAttrs &relocAttrs = target->getRelocAttrs(r.type);
+  const RelocAttrs &relocAttrs = getRelocAttrs(r.type);
 
   if (relocAttrs.hasAttr(RelocAttrBits::BRANCH)) {
     prepareBranchTarget(sym);
   } else if (relocAttrs.hasAttr(RelocAttrBits::GOT)) {
     if (relocAttrs.hasAttr(RelocAttrBits::POINTER) || needsBinding(sym))
       in.got->addEntry(sym);
   } else if (relocAttrs.hasAttr(RelocAttrBits::TLV)) {
     if (needsBinding(sym))
void Writer::scanRelocations() {
   for (InputSection *isec : inputSections) {
     if (isec->segname == segment_names::ld) {
       prepareCompactUnwind(isec);
       continue;
     }
 
     for (auto it = isec->relocs.begin(); it != isec->relocs.end(); ++it) {
       Reloc &r = *it;
-      if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
+      if (hasRelocAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
         // Skip over the following UNSIGNED relocation -- it's just there as the
         // minuend, and doesn't have the usual UNSIGNED semantics. We don't want
         // to emit rebase opcodes for it.
         it = std::next(it);
         assert(isa<Defined>(it->referent.dyn_cast<lld::macho::Symbol *>()));
         continue;
       }
       if (auto *sym = r.referent.dyn_cast<lld::macho::Symbol *>()) {