[lld-macho] Parallelize linker optimization hint processing

[BertalanD]

Summary

This commit moves the parsing of linker optimization hints into
ARM64::applyOptimizationHints. This lets us avoid allocating memory
for holding the parsed information, and moves work out of
ObjFile::parse, which is not parallelized at the moment.

This change reduces the overhead of processing LOHs to 25-30 ms when
linking Chromium Framework on my M1 machine; previously it took close to
100 ms.

There's no statistically significant change in runtime for a --threads=1
link.

Performance figures with all 8 cores utilized:

    N           Min           Max        Median           Avg        Stddev
x  20     3.8027232     3.8760762     3.8505335     3.8454145   0.026352574
+  20     3.7019017     3.8660538     3.7546209     3.7620371   0.032680043
Difference at 95.0% confidence
	-0.0833775 +/- 0.019
	-2.16823% +/- 0.494094%
	(Student's t, pooled s = 0.0296854)

[int3]

This change reduces the overhead of processing LOHs to 15-20 ms

Could you include what the previous overhead was?

lld/MachO/Arch/ARM64.cpp

552–557

nit: how about declaring this outside the loop and have it take p as a param?

maybe the compiler can optimize the code as-is, but it would be nice not to have to wonder about it + having parameters passed explicitly instead of by capture tends to make for more readable code (at least when the param list is small)

569–570

it would be nice to avoid macros where possible, especially when they change control flow... IMO this is clearer and doesn't take any extra lines

lld/test/MachO/invalid/invalid-loh.s

7–8

can rm this now that split-file is no longer used

[BertalanD]

Addressed review comments, tweaked the comment on applyOptimizationHints and updated the description to include that the previous overhead was close to 100 milliseconds.

[BertalanD]

lld/MachO/Arch/ARM64.cpp

569–570

Oh, right. This can just be a lambda in the outermost scope that captures section as sectionAddr.

[BertalanD]

Removed ObjFile::optimizationHints.

[oontvoo]

lld/MachO/Arch/ARM64.cpp

551–556

nit: does this have to be a lambda? can't it be a simple static function?

each spelling of a lambda will be a unique type - multipling with different instantiation of this forEachHint's template, we may end up with a quite a handful types.

708

delete this?

[BertalanD]

Changed the readValuelambda into a standalone function and removed a stray #undef.

[BertalanD]

lld/MachO/Arch/ARM64.cpp

708

oops

[thakis]

Nice!

lld/MachO/Arch/ARM64.cpp

675

Does this save a lot of time? Running the loop below and early-returning every time (if there's no AdrpAdrp) feels like it should be fairly fast, and most realistic programs have AdrpAdrps anyways (…right?). I'd probably remove this early return and this variable.

[BertalanD]

lld/MachO/Arch/ARM64.cpp

675

I checked the usual Chromium Framework repro file. Of the 29,126 objects that have *any* LOHs, only 4127 actually contain the AdrpAdrp kind. IMO it's worth keeping this check. Reading all these ULEB-encoded integers a second time is not a trivial task.

[int3]

lgtm

[thakis]

lld/MachO/Arch/ARM64.cpp

675

Sgtm

lld/MachO/Arch/ARM64.cpp

 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "mach-o/compact_unwind_encoding.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/Endian.h"
+#include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support::endian;
 using namespace lld;
 using namespace lld::macho;
 
 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;
 
   void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
                             uint64_t stubOffset, uint64_t selrefsVA,
                             uint64_t selectorIndex, uint64_t gotAddr,
                             uint64_t msgSendIndex) const override;
   void populateThunk(InputSection *thunk, Symbol *funcSym) override;
-  void applyOptimizationHints(uint8_t *,
-                              const ConcatInputSection *) const override;
+  void applyOptimizationHints(uint8_t *, const ObjFile &) 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

 struct Ldr {
   uint8_t destRegister;
   uint8_t baseRegister;
   uint8_t p2Size;
   bool isFloat;
   ExtendType extendType;
   int64_t offset;
 };
-
-class OptimizationHintContext {
-public:
-  OptimizationHintContext(uint8_t *buf, const ConcatInputSection *isec)
-      : buf(buf), isec(isec) {}
-
-  void applyAdrpAdd(uint64_t, uint64_t);
-  void applyAdrpAdrp(uint64_t, uint64_t);
-  void applyAdrpLdr(uint64_t, uint64_t);
-  void applyAdrpLdrGot(uint64_t, uint64_t);
-  void applyAdrpAddLdr(uint64_t, uint64_t, uint64_t);
-  void applyAdrpLdrGotLdr(uint64_t, uint64_t, uint64_t);
-
-private:
-  uint8_t *buf;
-  const ConcatInputSection *isec;
-};
 } // namespace
 
 static bool parseAdrp(uint32_t insn, Adrp &adrp) {
   if ((insn & 0x9f000000) != 0x90000000)
     return false;
   adrp.destRegister = insn & 0x1f;
   uint64_t immHi = (insn >> 5) & 0x7ffff;
   uint64_t immLo = (insn >> 29) & 0x3;

 // target is within the +/- 1 MiB range allowed by the adr's 21 bit signed
 // immediate offset.
 //
 //   adrp xN, _foo@PAGE
 //   add  xM, xN, _foo@PAGEOFF
 // ->
 //   adr  xM, _foo
 //   nop
-void OptimizationHintContext::applyAdrpAdd(uint64_t offset1, uint64_t offset2) {
+static void applyAdrpAdd(uint8_t *buf, const ConcatInputSection *isec,
+                         uint64_t offset1, uint64_t offset2) {
   uint32_t ins1 = read32le(buf + offset1);
   uint32_t ins2 = read32le(buf + offset2);
   Adrp adrp;
   Add add;
   if (!parseAdrp(ins1, adrp) || !parseAdd(ins2, add))
     return;
   if (adrp.destRegister != add.srcRegister)
     return;

 // Transforms two adrp instructions into a single adrp if their referent
 // addresses are located on the same 4096 byte page.
 //
 //   adrp xN, _foo@PAGE
 //   adrp xN, _bar@PAGE
 // ->
 //   adrp xN, _foo@PAGE
 //   nop
-void OptimizationHintContext::applyAdrpAdrp(uint64_t offset1,
-                                            uint64_t offset2) {
+static void applyAdrpAdrp(uint8_t *buf, const ConcatInputSection *isec,
+                          uint64_t offset1, uint64_t offset2) {
   uint32_t ins1 = read32le(buf + offset1);
   uint32_t ins2 = read32le(buf + offset2);
   Adrp adrp1, adrp2;
   if (!parseAdrp(ins1, adrp1) || !parseAdrp(ins2, adrp2))
     return;
   if (adrp1.destRegister != adrp2.destRegister)
     return;
 

 // load from a PC-relative address if it is 4-byte aligned and within +/- 1 MiB,
 // as ldr can encode a signed 19-bit offset that gets multiplied by 4.
 //
 //   adrp xN, _foo@PAGE
 //   ldr  xM, [xN, _foo@PAGEOFF]
 // ->
 //   nop
 //   ldr  xM, _foo
-void OptimizationHintContext::applyAdrpLdr(uint64_t offset1, uint64_t offset2) {
+static void applyAdrpLdr(uint8_t *buf, const ConcatInputSection *isec,
+                         uint64_t offset1, uint64_t offset2) {
   uint32_t ins1 = read32le(buf + offset1);
   uint32_t ins2 = read32le(buf + offset2);
   Adrp adrp;
   Ldr ldr;
   if (!parseAdrp(ins1, adrp) || !parseLdr(ins2, ldr))
     return;
   if (adrp.destRegister != ldr.baseRegister)
     return;
 
   uint64_t addr1 = isec->getVA() + offset1;
   uint64_t addr2 = isec->getVA() + offset2;
   uint64_t referent = pageBits(addr1) + adrp.addend + ldr.offset;
   ldr.offset = referent - addr2;
   if (!isLiteralLdrEligible(ldr))
     return;
 
   writeNop(buf + offset1);
   writeLiteralLdr(buf + offset2, ldr);
 }
 
 // GOT loads are emitted by the compiler as a pair of adrp and ldr instructions,
 // but they may be changed to adrp+add by relaxGotLoad(). This hint performs
 // the AdrpLdr or AdrpAdd transformation depending on whether it was relaxed.
-void OptimizationHintContext::applyAdrpLdrGot(uint64_t offset1,
-                                              uint64_t offset2) {
+static void applyAdrpLdrGot(uint8_t *buf, const ConcatInputSection *isec,
+                            uint64_t offset1, uint64_t offset2) {
   uint32_t ins2 = read32le(buf + offset2);
   Add add;
   Ldr ldr;
   if (parseAdd(ins2, add))
-    applyAdrpAdd(offset1, offset2);
+    applyAdrpAdd(buf, isec, offset1, offset2);
   else if (parseLdr(ins2, ldr))
-    applyAdrpLdr(offset1, offset2);
+    applyAdrpLdr(buf, isec, offset1, offset2);
 }
 
 // Optimizes an adrp+add+ldr sequence used for loading from a local symbol's
 // address by loading directly if it's close enough, or to an adrp(p)+ldr
 // sequence if it's not.
 //
 //   adrp x0, _foo@PAGE
 //   add  x1, x0, _foo@PAGEOFF
 //   ldr  x2, [x1, #off]
-void OptimizationHintContext::applyAdrpAddLdr(uint64_t offset1,
-                                              uint64_t offset2,
-                                              uint64_t offset3) {
+static void applyAdrpAddLdr(uint8_t *buf, const ConcatInputSection *isec,
+                            uint64_t offset1, uint64_t offset2,
   uint32_t ins1 = read32le(buf + offset1);
   Adrp adrp;
   if (!parseAdrp(ins1, adrp))
     return;
   uint32_t ins2 = read32le(buf + offset2);
   Add add;
   if (!parseAdd(ins2, add))
     return;
static void applyAdrpAddLdr(uint8_t *buf, const ConcatInputSection *isec,
   }
 }
 
 // Relaxes a GOT-indirect load.
 // If the referenced symbol is external and its GOT entry is within +/- 1 MiB,
 // the GOT entry can be loaded with a single literal ldr instruction.
 // If the referenced symbol is local and thus has been relaxed to adrp+add+ldr,
 // we perform the AdrpAddLdr transformation.
-void OptimizationHintContext::applyAdrpLdrGotLdr(uint64_t offset1,
-                                                 uint64_t offset2,
-                                                 uint64_t offset3) {
+static void applyAdrpLdrGotLdr(uint8_t *buf, const ConcatInputSection *isec,
+                               uint64_t offset1, uint64_t offset2,
   uint32_t ins2 = read32le(buf + offset2);
   Add add;
   Ldr ldr2;
 
   if (parseAdd(ins2, add)) {
-    applyAdrpAddLdr(offset1, offset2, offset3);
+    applyAdrpAddLdr(buf, isec, offset1, offset2, offset3);
   } else if (parseLdr(ins2, ldr2)) {
     // adrp x1, _foo@GOTPAGE
     // ldr  x2, [x1, _foo@GOTPAGEOFF]
     // ldr  x3, [x2, #off]
 
     uint32_t ins1 = read32le(buf + offset1);
     Adrp adrp;
     if (!parseAdrp(ins1, adrp))
if (parseAdd(ins2, add)) {
     literalLdr.offset = referent - addr2;
     if (isLiteralLdrEligible(literalLdr)) {
       writeNop(buf + offset1);
       writeLiteralLdr(buf + offset2, literalLdr);
     }
   }
 }
 
-void ARM64::applyOptimizationHints(uint8_t *buf,
-                                   const ConcatInputSection *isec) const {
-  assert(isec);
-
-  // Note: Some of these optimizations might not be valid when shared regions
-  // are in use. Will need to revisit this if splitSegInfo is added.
-
-  OptimizationHintContext ctx(buf, isec);
-  for (const OptimizationHint &hint : isec->optimizationHints) {
-    switch (hint.type) {
-    case LOH_ARM64_ADRP_ADRP:
-      // This is done in another pass because the other optimization hints
-      // might cause its targets to be turned into NOPs.
+static uint64_t readValue(const uint8_t *&ptr, const uint8_t *end) {
+  unsigned int n = 0;
+  uint64_t value = decodeULEB128(ptr, &n, end);
+  ptr += n;
+  return value;
+}
+
+template <typename Callback>
+static void forEachHint(ArrayRef<uint8_t> data, Callback callback) {
+  std::array<uint64_t, 3> args;
+
+  for (const uint8_t *p = data.begin(), *end = data.end(); p < end;) {
+    uint64_t type = readValue(p, end);
+    if (type == 0)
+      break;
+
+    uint64_t argCount = readValue(p, end);
+    // All known LOH types as of 2022-09 have 3 or fewer arguments; skip others.
+    if (argCount > 3) {
+      for (unsigned i = 0; i < argCount; ++i)
+        readValue(p, end);
+      continue;
+    }
+
+    for (unsigned i = 0; i < argCount; ++i)
+      args[i] = readValue(p, end);
+    callback(type, ArrayRef<uint64_t>(args.data(), argCount));
+  }
+}
+
+// On RISC architectures like arm64, materializing a memory address generally
+// takes multiple instructions. If the referenced symbol is located close enough
+// in memory, fewer instructions are needed.
+//
+// Linker optimization hints record where addresses are computed. After
+// addresses have been assigned, if possible, we change them to a shorter
+// sequence of instructions. The size of the binary is not modified; the
+// eliminated instructions are replaced with NOPs. This still leads to faster
+// code as the CPU can skip over NOPs quickly.
+//
+// LOHs are specified by the LC_LINKER_OPTIMIZATION_HINTS load command, which
+// points to a sequence of ULEB128-encoded numbers. Each entry specifies a
+// transformation kind, and 2 or 3 addresses where the instructions are located.
+void ARM64::applyOptimizationHints(uint8_t *outBuf, const ObjFile &obj) const {
+  ArrayRef<uint8_t> data = obj.getOptimizationHints();
+  if (data.empty())
+    return;
+
+  const ConcatInputSection *section = nullptr;
+  uint64_t sectionAddr = 0;
+  uint8_t *buf = nullptr;
+
+  auto findSection = [&](uint64_t addr) {
+    if (section && addr >= sectionAddr &&
+        addr < sectionAddr + section->getSize())
+      return true;
+
+    auto secIt = std::prev(llvm::upper_bound(
+        obj.sections, addr,
+        [](uint64_t off, const Section *sec) { return off < sec->addr; }));
+    const Section *sec = *secIt;
+
+    auto subsecIt = std::prev(llvm::upper_bound(
+        sec->subsections, addr - sec->addr,
+        [](uint64_t off, Subsection subsec) { return off < subsec.offset; }));
+    const Subsection &subsec = *subsecIt;
+    const ConcatInputSection *isec =
+        dyn_cast_or_null<ConcatInputSection>(subsec.isec);
+    if (!isec || isec->shouldOmitFromOutput())
+      return false;
+
+    section = isec;
+    sectionAddr = subsec.offset + sec->addr;
+    buf = outBuf + section->outSecOff + section->parent->fileOff;
+    return true;
+  };
+
+  auto isValidOffset = [&](uint64_t offset) {
+    if (offset < sectionAddr || offset >= sectionAddr + section->getSize()) {
+      error("linker optimization hint spans multiple sections");
+      return false;
+    }
+    return true;
+  };
+
+  bool hasAdrpAdrp = false;
+  forEachHint(data, [&](uint64_t kind, ArrayRef<uint64_t> args) {
+    if (kind == LOH_ARM64_ADRP_ADRP) {
+      hasAdrpAdrp = true;
+      return;
+    }
+
+    if (!findSection(args[0]))
+      return;
+    switch (kind) {
+    case LOH_ARM64_ADRP_ADD:
+      if (isValidOffset(args[1]))
+        applyAdrpAdd(buf, section, args[0] - sectionAddr,
+                     args[1] - sectionAddr);
       break;
     case LOH_ARM64_ADRP_LDR:
-      ctx.applyAdrpLdr(hint.offset0, hint.offset0 + hint.delta[0]);
+      if (isValidOffset(args[1]))
+        applyAdrpLdr(buf, section, args[0] - sectionAddr,
+                     args[1] - sectionAddr);
+      break;
+    case LOH_ARM64_ADRP_LDR_GOT:
+      if (isValidOffset(args[1]))
+        applyAdrpLdrGot(buf, section, args[0] - sectionAddr,
+                        args[1] - sectionAddr);
       break;
     case LOH_ARM64_ADRP_ADD_LDR:
-      ctx.applyAdrpAddLdr(hint.offset0, hint.offset0 + hint.delta[0],
-                          hint.offset0 + hint.delta[1]);
+      if (isValidOffset(args[1]) && isValidOffset(args[2]))
+        applyAdrpAddLdr(buf, section, args[0] - sectionAddr,
+                        args[1] - sectionAddr, args[2] - sectionAddr);
       break;
     case LOH_ARM64_ADRP_LDR_GOT_LDR:
-      ctx.applyAdrpLdrGotLdr(hint.offset0, hint.offset0 + hint.delta[0],
-                             hint.offset0 + hint.delta[1]);
+      if (isValidOffset(args[1]) && isValidOffset(args[2]))
+        applyAdrpLdrGotLdr(buf, section, args[0] - sectionAddr,
+                           args[1] - sectionAddr, args[2] - sectionAddr);
       break;
     case LOH_ARM64_ADRP_ADD_STR:
     case LOH_ARM64_ADRP_LDR_GOT_STR:
       // TODO: Implement these
       break;
-    case LOH_ARM64_ADRP_ADD:
-      ctx.applyAdrpAdd(hint.offset0, hint.offset0 + hint.delta[0]);
-      break;
-    case LOH_ARM64_ADRP_LDR_GOT:
-      ctx.applyAdrpLdrGot(hint.offset0, hint.offset0 + hint.delta[0]);
-      break;
-    }
     }
+  });
+
+  if (!hasAdrpAdrp)
+    return;
 
-  for (const OptimizationHint &hint : isec->optimizationHints)
-    if (hint.type == LOH_ARM64_ADRP_ADRP)
-      ctx.applyAdrpAdrp(hint.offset0, hint.offset0 + hint.delta[0]);
+  // AdrpAdrp optimization hints are performed in a second pass because they
+  // might interfere with other transformations. For instance, consider the
+  // following input:
+  //
+  //   adrp x0, _foo@PAGE
+  //   add  x1, x0, _foo@PAGEOFF
+  //   adrp x0, _bar@PAGE
+  //   add  x2, x0, _bar@PAGEOFF
+  //
+  // If we perform the AdrpAdrp relaxation first, we get:
+  //
+  //   adrp x0, _foo@PAGE
+  //   add  x1, x0, _foo@PAGEOFF
+  //   nop
+  //   add x2, x0, _bar@PAGEOFF
+  //
+  // If we then apply AdrpAdd to the first two instructions, the add will have a
+  // garbage value in x0:
+  //
+  //   adr  x1, _foo
+  //   nop
+  //   nop
+  //   add  x2, x0, _bar@PAGEOFF
+  forEachHint(data, [&](uint64_t kind, ArrayRef<uint64_t> args) {
+    if (kind != LOH_ARM64_ADRP_ADRP)
+      return;
+    if (!findSection(args[0]))
+      return;
+    if (isValidOffset(args[1]))
+      applyAdrpAdrp(buf, section, args[0] - sectionAddr, args[1] - sectionAddr);
+  });
 }
 
 TargetInfo *macho::createARM64TargetInfo() {
   static ARM64 t;
   return &t;
 }

lld/MachO/InputFiles.h

 };
 
 // .o file
 class ObjFile final : public InputFile {
 public:
   ObjFile(MemoryBufferRef mb, uint32_t modTime, StringRef archiveName,
           bool lazy = false, bool forceHidden = false);
   ArrayRef<llvm::MachO::data_in_code_entry> getDataInCode() const;
+  ArrayRef<uint8_t> getOptimizationHints() const;
   template <class LP> void parse();
 
   static bool classof(const InputFile *f) { return f->kind() == ObjKind; }
 
   std::string sourceFile() const;
   // Parses line table information for diagnostics. compileUnit should be used
   // for other purposes.
   lld::DWARFCache *getDwarf();
 
   llvm::DWARFUnit *compileUnit = nullptr;
   std::unique_ptr<lld::DWARFCache> dwarfCache;
   Section *addrSigSection = nullptr;
   const uint32_t modTime;
   bool forceHidden;
   std::vector<ConcatInputSection *> debugSections;
   std::vector<CallGraphEntry> callGraph;
   llvm::DenseMap<ConcatInputSection *, FDE> fdes;
-  std::vector<OptimizationHint> optimizationHints;
   std::vector<AliasSymbol *> aliases;
 
 private:
   llvm::once_flag initDwarf;
   template <class LP> void parseLazy();
   template <class SectionHeader> void parseSections(ArrayRef<SectionHeader>);
   template <class LP>
   void parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
                     ArrayRef<typename LP::nlist> nList, const char *strtab,
                     bool subsectionsViaSymbols);
   template <class NList>
   Symbol *parseNonSectionSymbol(const NList &sym, const char *strtab);
   template <class SectionHeader>
   void parseRelocations(ArrayRef<SectionHeader> sectionHeaders,
                         const SectionHeader &, Section &);
   void parseDebugInfo();
-  void parseOptimizationHints(ArrayRef<uint8_t> data);
   void splitEhFrames(ArrayRef<uint8_t> dataArr, Section &ehFrameSection);
   void registerCompactUnwind(Section &compactUnwindSection);
   void registerEhFrames(Section &ehFrameSection);
 };
 
 // command-line -sectcreate file
 class OpaqueFile final : public InputFile {
 public:

lld/MachO/InputFiles.cpp

static Defined *findSymbolAtOffset(const ConcatInputSection *isec,
   // The offset should point at the exact address of a symbol (with no addend.)
   if (it == isec->symbols.end() || (*it)->value != off) {
     assert(isec->wasCoalesced);
     return nullptr;
   }
   return *it;
 }
 
-// Linker optimization hints mark a sequence of instructions used for
-// synthesizing an address which that be transformed into a faster sequence. The
-// transformations depend on conditions that are determined at link time, like
-// the distance to the referenced symbol or its alignment.
-//
-// Each hint has a type and refers to 2 or 3 instructions. Each of those
-// instructions must have a corresponding relocation. After addresses have been
-// finalized and relocations have been performed, we check if the requirements
-// hold, and perform the optimizations if they do.
-//
-// Similar linker relaxations exist for ELF as well, with the difference being
-// that the explicit marking allows for the relaxation of non-consecutive
-// relocations too.
-//
-// The specific types of hints are documented in Arch/ARM64.cpp
-void ObjFile::parseOptimizationHints(ArrayRef<uint8_t> data) {
-  auto expectedArgCount = [](uint8_t type) {
-    switch (type) {
-    case LOH_ARM64_ADRP_ADRP:
-    case LOH_ARM64_ADRP_LDR:
-    case LOH_ARM64_ADRP_ADD:
-    case LOH_ARM64_ADRP_LDR_GOT:
-      return 2;
-    case LOH_ARM64_ADRP_ADD_LDR:
-    case LOH_ARM64_ADRP_ADD_STR:
-    case LOH_ARM64_ADRP_LDR_GOT_LDR:
-    case LOH_ARM64_ADRP_LDR_GOT_STR:
-      return 3;
-    }
-    return -1;
-  };
-
-  // Each hint contains at least 4 ULEB128-encoded fields, so in the worst case,
-  // there are data.size() / 4 LOHs. It's a huge overestimation though, as
-  // offsets are unlikely to fall in the 0-127 byte range, so we pre-allocate
-  // half as much.
-  optimizationHints.reserve(data.size() / 8);
-
-  for (const uint8_t *p = data.begin(); p < data.end();) {
-    const ptrdiff_t inputOffset = p - data.begin();
-    unsigned int n = 0;
-    uint8_t type = decodeULEB128(p, &n, data.end());
-    p += n;
-
-    // An entry of type 0 terminates the list.
-    if (type == 0)
-      break;
-
-    int expectedCount = expectedArgCount(type);
-    if (LLVM_UNLIKELY(expectedCount == -1)) {
-      error("Linker optimization hint at offset " + Twine(inputOffset) +
-            " has unknown type " + Twine(type));
-      return;
-    }
-
-    uint8_t argCount = decodeULEB128(p, &n, data.end());
-    p += n;
-
-    if (LLVM_UNLIKELY(argCount != expectedCount)) {
-      error("Linker optimization hint at offset " + Twine(inputOffset) +
-            " has " + Twine(argCount) + " arguments instead of the expected " +
-            Twine(expectedCount));
-      return;
-    }
-
-    uint64_t offset0 = decodeULEB128(p, &n, data.end());
-    p += n;
-
-    int16_t delta[2];
-    for (int i = 0; i < argCount - 1; ++i) {
-      uint64_t address = decodeULEB128(p, &n, data.end());
-      p += n;
-      int64_t d = address - offset0;
-      if (LLVM_UNLIKELY(d > std::numeric_limits<int16_t>::max() ||
-                        d < std::numeric_limits<int16_t>::min())) {
-        error("Linker optimization hint at offset " + Twine(inputOffset) +
-              " has addresses too far apart");
-        return;
-      }
-      delta[i] = d;
-    }
-
-    optimizationHints.push_back({offset0, {delta[0], delta[1]}, type});
-  }
-
-  // We sort the per-object vector of optimization hints so each section only
-  // needs to hold an ArrayRef to a contiguous range of hints.
-  llvm::sort(optimizationHints,
-             [](const OptimizationHint &a, const OptimizationHint &b) {
-               return a.offset0 < b.offset0;
-             });
-
-  auto section = sections.begin();
-  auto subsection = (*section)->subsections.begin();
-  uint64_t subsectionBase = 0;
-  uint64_t subsectionEnd = 0;
-
-  auto updateAddr = [&]() {
-    subsectionBase = (*section)->addr + subsection->offset;
-    subsectionEnd = subsectionBase + subsection->isec->getSize();
-  };
-
-  auto advanceSubsection = [&]() {
-    if (section == sections.end())
-      return;
-    ++subsection;
-    while (subsection == (*section)->subsections.end()) {
-      ++section;
-      if (section == sections.end())
-        return;
-      subsection = (*section)->subsections.begin();
-    }
-  };
-
-  updateAddr();
-  auto hintStart = optimizationHints.begin();
-  for (auto hintEnd = hintStart, end = optimizationHints.end(); hintEnd != end;
-       ++hintEnd) {
-    if (hintEnd->offset0 >= subsectionEnd) {
-      subsection->isec->optimizationHints =
-          ArrayRef<OptimizationHint>(&*hintStart, hintEnd - hintStart);
-
-      hintStart = hintEnd;
-      while (hintStart->offset0 >= subsectionEnd) {
-        advanceSubsection();
-        if (section == sections.end())
-          break;
-        updateAddr();
-        assert(hintStart->offset0 >= subsectionBase);
-      }
-    }
-
-    hintEnd->offset0 -= subsectionBase;
-    for (int i = 0, count = expectedArgCount(hintEnd->type); i < count - 1;
-         ++i) {
-      if (LLVM_UNLIKELY(
-              hintEnd->delta[i] < -static_cast<int64_t>(hintEnd->offset0) ||
-              hintEnd->delta[i] >=
-                  static_cast<int64_t>(subsectionEnd - hintEnd->offset0))) {
-        error("Linker optimization hint spans multiple sections");
-        return;
-      }
-    }
-  }
-  if (section != sections.end())
-    subsection->isec->optimizationHints = ArrayRef<OptimizationHint>(
-        &*hintStart, optimizationHints.end() - hintStart);
-}
-
 template <class SectionHeader>
 static bool validateRelocationInfo(InputFile *file, const SectionHeader &sec,
                                    relocation_info rel) {
   const RelocAttrs &relocAttrs = target->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 " +
template <class LP> void ObjFile::parse() {
   }
 
   // The relocations may refer to the symbols, so we parse them after we have
   // parsed all the symbols.
   for (size_t i = 0, n = sections.size(); i < n; ++i)
     if (!sections[i]->subsections.empty())
       parseRelocations(sectionHeaders, sectionHeaders[i], *sections[i]);
 
-  if (!config->ignoreOptimizationHints)
-    if (auto *cmd = findCommand<linkedit_data_command>(
-            hdr, LC_LINKER_OPTIMIZATION_HINT))
-      parseOptimizationHints({buf + cmd->dataoff, cmd->datasize});
-
   parseDebugInfo();
 
   Section *ehFrameSection = nullptr;
   Section *compactUnwindSection = nullptr;
   for (Section *sec : sections) {
     Section **s = StringSwitch<Section **>(sec->name)
                       .Case(section_names::compactUnwind, &compactUnwindSection)
                       .Case(section_names::ehFrame, &ehFrameSection)
ArrayRef<data_in_code_entry> ObjFile::getDataInCode() const {
   const load_command *cmd = findCommand(buf, LC_DATA_IN_CODE);
   if (!cmd)
     return {};
   const auto *c = reinterpret_cast<const linkedit_data_command *>(cmd);
   return {reinterpret_cast<const data_in_code_entry *>(buf + c->dataoff),
           c->datasize / sizeof(data_in_code_entry)};
 }
 
+ArrayRef<uint8_t> ObjFile::getOptimizationHints() const {
+  const auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
+  if (auto *cmd =
+          findCommand<linkedit_data_command>(buf, LC_LINKER_OPTIMIZATION_HINT))
+    return {buf + cmd->dataoff, cmd->datasize};
+  return {};
+}
+
 // Create pointers from symbols to their associated compact unwind entries.
 void ObjFile::registerCompactUnwind(Section &compactUnwindSection) {
   for (const Subsection &subsection : compactUnwindSection.subsections) {
     ConcatInputSection *isec = cast<ConcatInputSection>(subsection.isec);
     // Hack!! Each compact unwind entry (CUE) has its UNSIGNED relocations embed
     // their addends in its data. Thus if ICF operated naively and compared the
     // entire contents of each CUE, entries with identical unwind info but e.g.
     // belonging to different functions would never be considered equivalent. To

lld/MachO/InputSection.h

public:
   // keep the address of the symbol(s) in this section unique in the final
   // binary ?
   bool keepUnique = false;
   uint32_t align = 1;
 
   OutputSection *parent = nullptr;
   ArrayRef<uint8_t> data;
   std::vector<Reloc> relocs;
-  ArrayRef<OptimizationHint> optimizationHints;
   // The symbols that belong to this InputSection, sorted by value. With
   // .subsections_via_symbols, there is typically only one element here.
   llvm::TinyPtrVector<Defined *> symbols;
 
 protected:
   const Section &section;
 
   const Defined *getContainingSymbol(uint64_t off) const;

lld/MachO/InputSection.cpp

 using namespace llvm::MachO;
 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
 // Verify ConcatInputSection's size on 64-bit builds. The size of std::vector
 // can differ based on STL debug levels (e.g. iterator debugging on MSVC's STL),
 // so account for that.
-static_assert(sizeof(void *) != 8 || sizeof(ConcatInputSection) ==
-                                         sizeof(std::vector<Reloc>) + 104,
+static_assert(sizeof(void *) != 8 ||
+                  sizeof(ConcatInputSection) == sizeof(std::vector<Reloc>) + 88,
               "Try to minimize ConcatInputSection's size, we create many "
               "instances of it");
 
 std::vector<ConcatInputSection *> macho::inputSections;
 
 uint64_t InputSection::getFileSize() const {
   return isZeroFill(getFlags()) ? 0 : getSize();
 }
if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
           referentVA -= firstTLVDataSection->addr;
       }
     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
       assert(!::shouldOmitFromOutput(referentIsec));
       referentVA = referentIsec->getVA(r.addend);
     }
     target->relocateOne(loc, r, referentVA, getVA() + r.offset);
   }
-
-  target->applyOptimizationHints(buf, this);
 }
 
 ConcatInputSection *macho::makeSyntheticInputSection(StringRef segName,
                                                      StringRef sectName,
                                                      uint32_t flags,
                                                      ArrayRef<uint8_t> data,
                                                      uint32_t align) {
   Section &section =

lld/MachO/Relocations.h

struct Reloc {
   Reloc() = default;
 
   Reloc(uint8_t type, bool pcrel, uint8_t length, uint32_t offset,
         int64_t addend, llvm::PointerUnion<Symbol *, InputSection *> referent)
       : type(type), pcrel(pcrel), length(length), offset(offset),
         addend(addend), referent(referent) {}
 };
 
-struct OptimizationHint {
-  // Offset of the first address within the containing InputSection.
-  uint64_t offset0;
-  // Offset of the other addresses relative to the first one.
-  int16_t delta[2];
-  uint8_t type;
-};
-
 bool validateSymbolRelocation(const Symbol *, const InputSection *,
                               const Reloc &);
 
 /*
  * v: The value the relocation is attempting to encode
  * bits: The number of bits actually available to encode this relocation
  */
 void reportRangeError(void *loc, const Reloc &, const llvm::Twine &v,

lld/MachO/Target.h

 
 namespace lld::macho {
 LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE();
 
 class Symbol;
 class Defined;
 class DylibSymbol;
 class InputSection;
-class ConcatInputSection;
+class ObjFile;
 
 class TargetInfo {
 public:
   template <class LP> TargetInfo(LP) {
     // Having these values available in TargetInfo allows us to access them
     // without having to resort to templates.
     magic = LP::magic;
     pageZeroSize = LP::pageZeroSize;
public:
   // For now, handleDtraceReloc only implements -no_dtrace_dof, and ensures
   // that the linking would not fail even when there are user-provided dtrace
   // symbols. However, unlike ld64, lld currently does not emit __dof sections.
   virtual void handleDtraceReloc(const Symbol *sym, const Reloc &r,
                                  uint8_t *loc) const {
     llvm_unreachable("Unsupported architecture for dtrace symbols");
   }
 
-  virtual void applyOptimizationHints(uint8_t *buf,
-                                      const ConcatInputSection *) const {};
+  virtual void applyOptimizationHints(uint8_t *, const ObjFile &) const {};
 
   uint32_t magic;
   llvm::MachO::CPUType cpuType;
   uint32_t cpuSubtype;
 
   uint64_t pageZeroSize;
   size_t headerSize;
   size_t stubSize;

lld/MachO/Writer.cpp

public:
   template <class LP> void createOutputSections();
   template <class LP> void createLoadCommands();
   void finalizeAddresses();
   void finalizeLinkEditSegment();
   void assignAddresses(OutputSegment *);
 
   void openFile();
   void writeSections();
+  void applyOptimizationHints();
   void writeUuid();
   void writeCodeSignature();
   void writeOutputFile();
 
   template <class LP> void run();
 
   ThreadPool threadPool;
   std::unique_ptr<FileOutputBuffer> &buffer;
void Writer::writeSections() {
   for (const OutputSegment *seg : outputSegments)
     append_range(osecs, seg->getSections());
 
   parallelForEach(osecs.begin(), osecs.end(), [&](const OutputSection *osec) {
     osec->writeTo(buf + osec->fileOff);
   });
 }
 
+void Writer::applyOptimizationHints() {
+  if (config->arch() != AK_arm64 || config->ignoreOptimizationHints)
+    return;
+
+  uint8_t *buf = buffer->getBufferStart();
+  TimeTraceScope timeScope("Apply linker optimization hints");
+  parallelForEach(inputFiles, [buf](const InputFile *file) {
+    if (const auto *objFile = dyn_cast<ObjFile>(file))
+      target->applyOptimizationHints(buf, *objFile);
+  });
+}
+
 // In order to utilize multiple cores, we first split the buffer into chunks,
 // compute a hash for each chunk, and then compute a hash value of the hash
 // values.
 void Writer::writeUuid() {
   TimeTraceScope timeScope("Computing UUID");
 
   ArrayRef<uint8_t> data{buffer->getBufferStart(), buffer->getBufferEnd()};
   unsigned chunkCount = parallel::strategy.compute_thread_count() * 10;

 
 void Writer::writeOutputFile() {
   TimeTraceScope timeScope("Write output file");
   openFile();
   reportPendingUndefinedSymbols();
   if (errorCount())
     return;
   writeSections();
+  applyOptimizationHints();
   writeUuid();
   writeCodeSignature();
 
   if (auto e = buffer->commit())
     fatal("failed to write output '" + buffer->getPath() +
           "': " + toString(std::move(e)));
 }
 

lld/test/MachO/invalid/invalid-loh.s

 # REQUIRES: aarch64
 
-# RUN: rm -rf %t; split-file %s %t
-# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/section.s -o %t/section.o
-# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/far.s -o %t/far.o
-# RUN: not %lld -arch arm64 %t/section.o -o /dev/null 2>&1 | FileCheck %s --check-prefix=SECTION
-# RUN: not %lld -arch arm64 %t/far.o -o /dev/null 2>&1 | FileCheck %s --check-prefix=FAR
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %s -o %t.o
+# RUN: not %lld -arch arm64 %t.o -o /dev/null 2>&1 | FileCheck %s
 
-# SECTION: error: Linker optimization hint spans multiple sections
-# FAR:     error: Linker optimization hint at offset 0 has addresses too far apart
+# CHECK: error: linker optimization hint spans multiple sections
 
-#--- section.s
 .globl _main
 _main:
 L1:
   adrp x0, _target@PAGE
 
 _foo:
 L2:
   add x0, x0, _target@PAGEOFF
 
 _target:
 
 .loh AdrpAdd L1, L2
 .subsections_via_symbols
-
-#--- far.s
-.globl _main
-_main:
-L1:
-  adrp x0, _target@PAGE
-  .zero 0x8000
-L2:
-  add  x0, x0, _target@PAGEOFF
-
-_target:
-
-.loh AdrpAdd L1, L2
-.subsections_via_symbols

lld/test/MachO/loh-adrp-adrp.s

 # CHECK-NEXT: adrp x1
 # CHECK-NEXT: adrp x2
 ## Not on the same page
 # CHECK-NEXT: adrp x3
 # CHECK-NEXT: adrp x3
 ## Not an adrp instruction (invalid)
 # CHECK-NEXT: nop
 # CHECK-NEXT: adrp x4
+## Other relaxations take precedence over AdrpAdrp
+# CHECK-NEXT: adr x6
+# CHECK-NEXT: nop
+# CHECK-NEXT: adr x6
+# CHECK-NEXT: nop
 
 .text
 .align 2
 
 .globl _main
 _main:
 L1:
   adrp x0, _foo@PAGE
 L2:
   adrp x0, _bar@PAGE
 L3:
   adrp x1, _foo@PAGE
 L4:
   adrp x2, _bar@PAGE
 L5:
   adrp x3, _foo@PAGE
 L6:
   adrp x3, _baz@PAGE
 L7:
   nop
 L8:
   adrp x4, _baz@PAGE
+L9:
+  adrp x5, _foo@PAGE
+L10:
+  add  x6, x5, _foo@PAGEOFF
+L11:
+  adrp x5, _bar@PAGE
+L12:
+  add  x6, x5, _bar@PAGEOFF
 
 .data
 .align 12
 _foo:
   .byte 0
 _bar:
   .byte 0
 .space 4094
 _baz:
   .byte 0
 
 .loh AdrpAdrp L1, L2
 .loh AdrpAdrp L3, L4
 .loh AdrpAdrp L5, L6
 .loh AdrpAdrp L7, L8
+.loh AdrpAdrp L9, L11
+.loh AdrpAdd  L9, L10
+.loh AdrpAdd  L11, L12