lld/MachO/Arch/ARM64.cpp

   1 //===- ARM64.cpp ----------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "Arch/ARM64Common.h"
  10 #include "InputFiles.h"
  11 #include "Symbols.h"
  12 #include "SyntheticSections.h"
  13 #include "Target.h"
  14
  15 #include "lld/Common/ErrorHandler.h"
  16 #include "mach-o/compact_unwind_encoding.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/BinaryFormat/MachO.h"
  20 #include "llvm/Support/Endian.h"
  21 #include "llvm/Support/LEB128.h"
  22 #include "llvm/Support/MathExtras.h"
  23
  24 using namespace llvm;
  25 using namespace llvm::MachO;
  26 using namespace llvm::support::endian;
  27 using namespace lld;
  28 using namespace lld::macho;
  29
  30 namespace {
  31
  32 struct ARM64 : ARM64Common {
  33   ARM64();
  34   void writeStub(uint8_t *buf, const Symbol &, uint64_t) const override;
  35   void writeStubHelperHeader(uint8_t *buf) const override;
  36   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
  37                             uint64_t entryAddr) const override;
  38
  39   void writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
  40                             uint64_t stubOffset, uint64_t selrefsVA,
  41                             uint64_t selectorIndex, uint64_t gotAddr,
  42                             uint64_t msgSendIndex) const override;
  43   void populateThunk(InputSection *thunk, Symbol *funcSym) override;
  44   void applyOptimizationHints(uint8_t *, const ObjFile &) const override;
  45 };
  46
  47 } // namespace
  48
  49 // Random notes on reloc types:
  50 // ADDEND always pairs with BRANCH26, PAGE21, or PAGEOFF12
  51 // POINTER_TO_GOT: ld64 supports a 4-byte pc-relative form as well as an 8-byte
  52 // absolute version of this relocation. The semantics of the absolute relocation
  53 // are weird -- it results in the value of the GOT slot being written, instead
  54 // of the address. Let's not support it unless we find a real-world use case.
  55 static constexpr std::array<RelocAttrs, 11> relocAttrsArray{{
  56 #define B(x) RelocAttrBits::x
  57     {"UNSIGNED",
  58      B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
  59     {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
  60     {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
  61     {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
  62     {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
  63     {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
  64     {"GOT_LOAD_PAGEOFF12",
  65      B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
  66     {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
  67     {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},
  68     {"TLVP_LOAD_PAGEOFF12",
  69      B(ABSOLUTE) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
  70     {"ADDEND", B(ADDEND)},
  71 #undef B
  72 }};
  73
  74 static constexpr uint32_t stubCode[] = {
  75     0x90000010, // 00: adrp  x16, __la_symbol_ptr@page
  76     0xf9400210, // 04: ldr   x16, [x16, __la_symbol_ptr@pageoff]
  77     0xd61f0200, // 08: br    x16
  78 };
  79
  80 void ARM64::writeStub(uint8_t *buf8, const Symbol &sym,
  81                       uint64_t pointerVA) const {
  82   ::writeStub(buf8, stubCode, sym, pointerVA);
  83 }
  84
  85 static constexpr uint32_t stubHelperHeaderCode[] = {
  86     0x90000011, // 00: adrp  x17, _dyld_private@page
  87     0x91000231, // 04: add   x17, x17, _dyld_private@pageoff
  88     0xa9bf47f0, // 08: stp   x16/x17, [sp, #-16]!
  89     0x90000010, // 0c: adrp  x16, dyld_stub_binder@page
  90     0xf9400210, // 10: ldr   x16, [x16, dyld_stub_binder@pageoff]
  91     0xd61f0200, // 14: br    x16
  92 };
  93
  94 void ARM64::writeStubHelperHeader(uint8_t *buf8) const {
  95   ::writeStubHelperHeader<LP64>(buf8, stubHelperHeaderCode);
  96 }
  97
  98 static constexpr uint32_t stubHelperEntryCode[] = {
  99     0x18000050, // 00: ldr  w16, l0
 100     0x14000000, // 04: b    stubHelperHeader
 101     0x00000000, // 08: l0: .long 0
 102 };
 103
 104 void ARM64::writeStubHelperEntry(uint8_t *buf8, const Symbol &sym,
 105                                  uint64_t entryVA) const {
 106   ::writeStubHelperEntry(buf8, stubHelperEntryCode, sym, entryVA);
 107 }
 108
 109 static constexpr uint32_t objcStubsFastCode[] = {
 110     0x90000001, // adrp  x1, __objc_selrefs@page
 111     0xf9400021, // ldr   x1, [x1, @selector("foo")@pageoff]
 112     0x90000010, // adrp  x16, _got@page
 113     0xf9400210, // ldr   x16, [x16, _objc_msgSend@pageoff]
 114     0xd61f0200, // br    x16
 115     0xd4200020, // brk   #0x1
 116     0xd4200020, // brk   #0x1
 117     0xd4200020, // brk   #0x1
 118 };
 119
 120 void ARM64::writeObjCMsgSendStub(uint8_t *buf, Symbol *sym, uint64_t stubsAddr,
 121                                  uint64_t stubOffset, uint64_t selrefsVA,
 122                                  uint64_t selectorIndex, uint64_t gotAddr,
 123                                  uint64_t msgSendIndex) const {
 124   ::writeObjCMsgSendStub<LP64>(buf, objcStubsFastCode, sym, stubsAddr,
 125                                stubOffset, selrefsVA, selectorIndex, gotAddr,
 126                                msgSendIndex);
 127 }
 128
 129 // A thunk is the relaxed variation of stubCode. We don't need the
 130 // extra indirection through a lazy pointer because the target address
 131 // is known at link time.
 132 static constexpr uint32_t thunkCode[] = {
 133     0x90000010, // 00: adrp  x16, <thunk.ptr>@page
 134     0x91000210, // 04: add   x16, [x16,<thunk.ptr>@pageoff]
 135     0xd61f0200, // 08: br    x16
 136 };
 137
 138 void ARM64::populateThunk(InputSection *thunk, Symbol *funcSym) {
 139   thunk->align = 4;
 140   thunk->data = {reinterpret_cast<const uint8_t *>(thunkCode),
 141                  sizeof(thunkCode)};
 142   thunk->relocs.emplace_back(/*type=*/ARM64_RELOC_PAGEOFF12,
 143                              /*pcrel=*/false, /*length=*/2,
 144                              /*offset=*/4, /*addend=*/0,
 145                              /*referent=*/funcSym);
 146   thunk->relocs.emplace_back(/*type=*/ARM64_RELOC_PAGE21,
 147                              /*pcrel=*/true, /*length=*/2,
 148                              /*offset=*/0, /*addend=*/0,
 149                              /*referent=*/funcSym);
 150 }
 151
 152 ARM64::ARM64() : ARM64Common(LP64()) {
 153   cpuType = CPU_TYPE_ARM64;
 154   cpuSubtype = CPU_SUBTYPE_ARM64_ALL;
 155
 156   stubSize = sizeof(stubCode);
 157   thunkSize = sizeof(thunkCode);
 158
 159   objcStubsFastSize = sizeof(objcStubsFastCode);
 160   objcStubsAlignment = 32;
 161
 162   // Branch immediate is two's complement 26 bits, which is implicitly
 163   // multiplied by 4 (since all functions are 4-aligned: The branch range
 164   // is -4*(2**(26-1))..4*(2**(26-1) - 1).
 165   backwardBranchRange = 128 * 1024 * 1024;
 166   forwardBranchRange = backwardBranchRange - 4;
 167
 168   modeDwarfEncoding = UNWIND_ARM64_MODE_DWARF;
 169   subtractorRelocType = ARM64_RELOC_SUBTRACTOR;
 170   unsignedRelocType = ARM64_RELOC_UNSIGNED;
 171
 172   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
 173   stubHelperEntrySize = sizeof(stubHelperEntryCode);
 174
 175   relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
 176 }
 177
 178 namespace {
 179 struct Adrp {
 180   uint32_t destRegister;
 181   int64_t addend;
 182 };
 183
 184 struct Add {
 185   uint8_t destRegister;
 186   uint8_t srcRegister;
 187   uint32_t addend;
 188 };
 189
 190 enum ExtendType { ZeroExtend = 1, Sign64 = 2, Sign32 = 3 };
 191
 192 struct Ldr {
 193   uint8_t destRegister;
 194   uint8_t baseRegister;
 195   uint8_t p2Size;
 196   bool isFloat;
 197   ExtendType extendType;
 198   int64_t offset;
 199 };
 200 } // namespace
 201
 202 static bool parseAdrp(uint32_t insn, Adrp &adrp) {
 203   if ((insn & 0x9f000000) != 0x90000000)
 204     return false;
 205   adrp.destRegister = insn & 0x1f;
 206   uint64_t immHi = (insn >> 5) & 0x7ffff;
 207   uint64_t immLo = (insn >> 29) & 0x3;
 208   adrp.addend = SignExtend64<21>(immLo | (immHi << 2)) * 4096;
 209   return true;
 210 }
 211
 212 static bool parseAdd(uint32_t insn, Add &add) {
 213   if ((insn & 0xffc00000) != 0x91000000)
 214     return false;
 215   add.destRegister = insn & 0x1f;
 216   add.srcRegister = (insn >> 5) & 0x1f;
 217   add.addend = (insn >> 10) & 0xfff;
 218   return true;
 219 }
 220
 221 static bool parseLdr(uint32_t insn, Ldr &ldr) {
 222   ldr.destRegister = insn & 0x1f;
 223   ldr.baseRegister = (insn >> 5) & 0x1f;
 224   uint8_t size = insn >> 30;
 225   uint8_t opc = (insn >> 22) & 3;
 226
 227   if ((insn & 0x3fc00000) == 0x39400000) {
 228     // LDR (immediate), LDRB (immediate), LDRH (immediate)
 229     ldr.p2Size = size;
 230     ldr.extendType = ZeroExtend;
 231     ldr.isFloat = false;
 232   } else if ((insn & 0x3f800000) == 0x39800000) {
 233     // LDRSB (immediate), LDRSH (immediate), LDRSW (immediate)
 234     ldr.p2Size = size;
 235     ldr.extendType = static_cast<ExtendType>(opc);
 236     ldr.isFloat = false;
 237   } else if ((insn & 0x3f400000) == 0x3d400000) {
 238     // LDR (immediate, SIMD&FP)
 239     ldr.extendType = ZeroExtend;
 240     ldr.isFloat = true;
 241     if (opc == 1)
 242       ldr.p2Size = size;
 243     else if (size == 0 && opc == 3)
 244       ldr.p2Size = 4;
 245     else
 246       return false;
 247   } else {
 248     return false;
 249   }
 250   ldr.offset = ((insn >> 10) & 0xfff) << ldr.p2Size;
 251   return true;
 252 }
 253
 254 static bool isValidAdrOffset(int32_t delta) { return isInt<21>(delta); }
 255
 256 static void writeAdr(void *loc, uint32_t dest, int32_t delta) {
 257   assert(isValidAdrOffset(delta));
 258   uint32_t opcode = 0x10000000;
 259   uint32_t immHi = (delta & 0x001ffffc) << 3;
 260   uint32_t immLo = (delta & 0x00000003) << 29;
 261   write32le(loc, opcode | immHi | immLo | dest);
 262 }
 263
 264 static void writeNop(void *loc) { write32le(loc, 0xd503201f); }
 265
 266 static bool isLiteralLdrEligible(const Ldr &ldr) {
 267   return ldr.p2Size > 1 && isShiftedInt<19, 2>(ldr.offset);
 268 }
 269
 270 static void writeLiteralLdr(void *loc, const Ldr &ldr) {
 271   assert(isLiteralLdrEligible(ldr));
 272   uint32_t imm19 = (ldr.offset / 4 & maskTrailingOnes<uint32_t>(19)) << 5;
 273   uint32_t opcode;
 274   switch (ldr.p2Size) {
 275   case 2:
 276     if (ldr.isFloat)
 277       opcode = 0x1c000000;
 278     else
 279       opcode = ldr.extendType == Sign64 ? 0x98000000 : 0x18000000;
 280     break;
 281   case 3:
 282     opcode = ldr.isFloat ? 0x5c000000 : 0x58000000;
 283     break;
 284   case 4:
 285     opcode = 0x9c000000;
 286     break;
 287   default:
 288     llvm_unreachable("Invalid literal ldr size");
 289   }
 290   write32le(loc, opcode | imm19 | ldr.destRegister);
 291 }
 292
 293 static bool isImmediateLdrEligible(const Ldr &ldr) {
 294   // Note: We deviate from ld64's behavior, which converts to immediate loads
 295   // only if ldr.offset < 4096, even though the offset is divided by the load's
 296   // size in the 12-bit immediate operand. Only the unsigned offset variant is
 297   // supported.
 298
 299   uint32_t size = 1 << ldr.p2Size;
 300   return ldr.offset >= 0 && (ldr.offset % size) == 0 &&
 301          isUInt<12>(ldr.offset >> ldr.p2Size);
 302 }
 303
 304 static void writeImmediateLdr(void *loc, const Ldr &ldr) {
 305   assert(isImmediateLdrEligible(ldr));
 306   uint32_t opcode = 0x39000000;
 307   if (ldr.isFloat) {
 308     opcode |= 0x04000000;
 309     assert(ldr.extendType == ZeroExtend);
 310   }
 311   opcode |= ldr.destRegister;
 312   opcode |= ldr.baseRegister << 5;
 313   uint8_t size, opc;
 314   if (ldr.p2Size == 4) {
 315     size = 0;
 316     opc = 3;
 317   } else {
 318     opc = ldr.extendType;
 319     size = ldr.p2Size;
 320   }
 321   uint32_t immBits = ldr.offset >> ldr.p2Size;
 322   write32le(loc, opcode | (immBits << 10) | (opc << 22) | (size << 30));
 323 }
 324
 325 // Transforms a pair of adrp+add instructions into an adr instruction if the
 326 // target is within the +/- 1 MiB range allowed by the adr's 21 bit signed
 327 // immediate offset.
 328 //
 329 //   adrp xN, _foo@PAGE
 330 //   add  xM, xN, _foo@PAGEOFF
 331 // ->
 332 //   adr  xM, _foo
 333 //   nop
 334 static void applyAdrpAdd(uint8_t *buf, const ConcatInputSection *isec,
 335                          uint64_t offset1, uint64_t offset2) {
 336   uint32_t ins1 = read32le(buf + offset1);
 337   uint32_t ins2 = read32le(buf + offset2);
 338   Adrp adrp;
 339   Add add;
 340   if (!parseAdrp(ins1, adrp) || !parseAdd(ins2, add))
 341     return;
 342   if (adrp.destRegister != add.srcRegister)
 343     return;
 344
 345   uint64_t addr1 = isec->getVA() + offset1;
 346   uint64_t referent = pageBits(addr1) + adrp.addend + add.addend;
 347   int64_t delta = referent - addr1;
 348   if (!isValidAdrOffset(delta))
 349     return;
 350
 351   writeAdr(buf + offset1, add.destRegister, delta);
 352   writeNop(buf + offset2);
 353 }
 354
 355 // Transforms two adrp instructions into a single adrp if their referent
 356 // addresses are located on the same 4096 byte page.
 357 //
 358 //   adrp xN, _foo@PAGE
 359 //   adrp xN, _bar@PAGE
 360 // ->
 361 //   adrp xN, _foo@PAGE
 362 //   nop
 363 static void applyAdrpAdrp(uint8_t *buf, const ConcatInputSection *isec,
 364                           uint64_t offset1, uint64_t offset2) {
 365   uint32_t ins1 = read32le(buf + offset1);
 366   uint32_t ins2 = read32le(buf + offset2);
 367   Adrp adrp1, adrp2;
 368   if (!parseAdrp(ins1, adrp1) || !parseAdrp(ins2, adrp2))
 369     return;
 370   if (adrp1.destRegister != adrp2.destRegister)
 371     return;
 372
 373   uint64_t page1 = pageBits(offset1 + isec->getVA()) + adrp1.addend;
 374   uint64_t page2 = pageBits(offset2 + isec->getVA()) + adrp2.addend;
 375   if (page1 != page2)
 376     return;
 377
 378   writeNop(buf + offset2);
 379 }
 380
 381 // Transforms a pair of adrp+ldr (immediate) instructions into an ldr (literal)
 382 // load from a PC-relative address if it is 4-byte aligned and within +/- 1 MiB,
 383 // as ldr can encode a signed 19-bit offset that gets multiplied by 4.
 384 //
 385 //   adrp xN, _foo@PAGE
 386 //   ldr  xM, [xN, _foo@PAGEOFF]
 387 // ->
 388 //   nop
 389 //   ldr  xM, _foo
 390 static void applyAdrpLdr(uint8_t *buf, const ConcatInputSection *isec,
 391                          uint64_t offset1, uint64_t offset2) {
 392   uint32_t ins1 = read32le(buf + offset1);
 393   uint32_t ins2 = read32le(buf + offset2);
 394   Adrp adrp;
 395   Ldr ldr;
 396   if (!parseAdrp(ins1, adrp) || !parseLdr(ins2, ldr))
 397     return;
 398   if (adrp.destRegister != ldr.baseRegister)
 399     return;
 400
 401   uint64_t addr1 = isec->getVA() + offset1;
 402   uint64_t addr2 = isec->getVA() + offset2;
 403   uint64_t referent = pageBits(addr1) + adrp.addend + ldr.offset;
 404   ldr.offset = referent - addr2;
 405   if (!isLiteralLdrEligible(ldr))
 406     return;
 407
 408   writeNop(buf + offset1);
 409   writeLiteralLdr(buf + offset2, ldr);
 410 }
 411
 412 // GOT loads are emitted by the compiler as a pair of adrp and ldr instructions,
 413 // but they may be changed to adrp+add by relaxGotLoad(). This hint performs
 414 // the AdrpLdr or AdrpAdd transformation depending on whether it was relaxed.
 415 static void applyAdrpLdrGot(uint8_t *buf, const ConcatInputSection *isec,
 416                             uint64_t offset1, uint64_t offset2) {
 417   uint32_t ins2 = read32le(buf + offset2);
 418   Add add;
 419   Ldr ldr;
 420   if (parseAdd(ins2, add))
 421     applyAdrpAdd(buf, isec, offset1, offset2);
 422   else if (parseLdr(ins2, ldr))
 423     applyAdrpLdr(buf, isec, offset1, offset2);
 424 }
 425
 426 // Optimizes an adrp+add+ldr sequence used for loading from a local symbol's
 427 // address by loading directly if it's close enough, or to an adrp(p)+ldr
 428 // sequence if it's not.
 429 //
 430 //   adrp x0, _foo@PAGE
 431 //   add  x1, x0, _foo@PAGEOFF
 432 //   ldr  x2, [x1, #off]
 433 static void applyAdrpAddLdr(uint8_t *buf, const ConcatInputSection *isec,
 434                             uint64_t offset1, uint64_t offset2,
 435                             uint64_t offset3) {
 436   uint32_t ins1 = read32le(buf + offset1);
 437   Adrp adrp;
 438   if (!parseAdrp(ins1, adrp))
 439     return;
 440   uint32_t ins2 = read32le(buf + offset2);
 441   Add add;
 442   if (!parseAdd(ins2, add))
 443     return;
 444   uint32_t ins3 = read32le(buf + offset3);
 445   Ldr ldr;
 446   if (!parseLdr(ins3, ldr))
 447     return;
 448   if (adrp.destRegister != add.srcRegister)
 449     return;
 450   if (add.destRegister != ldr.baseRegister)
 451     return;
 452
 453   // Load from the target address directly.
 454   //   nop
 455   //   nop
 456   //   ldr x2, [_foo + #off]
 457   uint64_t addr1 = isec->getVA() + offset1;
 458   uint64_t addr3 = isec->getVA() + offset3;
 459   uint64_t referent = pageBits(addr1) + adrp.addend + add.addend;
 460   Ldr literalLdr = ldr;
 461   literalLdr.offset += referent - addr3;
 462   if (isLiteralLdrEligible(literalLdr)) {
 463     writeNop(buf + offset1);
 464     writeNop(buf + offset2);
 465     writeLiteralLdr(buf + offset3, literalLdr);
 466     return;
 467   }
 468
 469   // Load the target address into a register and load from there indirectly.
 470   //   adr x1, _foo
 471   //   nop
 472   //   ldr x2, [x1, #off]
 473   int64_t adrOffset = referent - addr1;
 474   if (isValidAdrOffset(adrOffset)) {
 475     writeAdr(buf + offset1, ldr.baseRegister, adrOffset);
 476     // Note: ld64 moves the offset into the adr instruction for AdrpAddLdr, but
 477     // not for AdrpLdrGotLdr. Its effect is the same either way.
 478     writeNop(buf + offset2);
 479     return;
 480   }
 481
 482   // Move the target's page offset into the ldr's immediate offset.
 483   //   adrp x0, _foo@PAGE
 484   //   nop
 485   //   ldr x2, [x0, _foo@PAGEOFF + #off]
 486   Ldr immediateLdr = ldr;
 487   immediateLdr.baseRegister = adrp.destRegister;
 488   immediateLdr.offset += add.addend;
 489   if (isImmediateLdrEligible(immediateLdr)) {
 490     writeNop(buf + offset2);
 491     writeImmediateLdr(buf + offset3, immediateLdr);
 492     return;
 493   }
 494 }
 495
 496 // Relaxes a GOT-indirect load.
 497 // If the referenced symbol is external and its GOT entry is within +/- 1 MiB,
 498 // the GOT entry can be loaded with a single literal ldr instruction.
 499 // If the referenced symbol is local and thus has been relaxed to adrp+add+ldr,
 500 // we perform the AdrpAddLdr transformation.
 501 static void applyAdrpLdrGotLdr(uint8_t *buf, const ConcatInputSection *isec,
 502                                uint64_t offset1, uint64_t offset2,
 503                                uint64_t offset3) {
 504   uint32_t ins2 = read32le(buf + offset2);
 505   Add add;
 506   Ldr ldr2;
 507
 508   if (parseAdd(ins2, add)) {
 509     applyAdrpAddLdr(buf, isec, offset1, offset2, offset3);
 510   } else if (parseLdr(ins2, ldr2)) {
 511     // adrp x1, _foo@GOTPAGE
 512     // ldr  x2, [x1, _foo@GOTPAGEOFF]
 513     // ldr  x3, [x2, #off]
 514
 515     uint32_t ins1 = read32le(buf + offset1);
 516     Adrp adrp;
 517     if (!parseAdrp(ins1, adrp))
 518       return;
 519     uint32_t ins3 = read32le(buf + offset3);
 520     Ldr ldr3;
 521     if (!parseLdr(ins3, ldr3))
 522       return;
 523
 524     if (ldr2.baseRegister != adrp.destRegister)
 525       return;
 526     if (ldr3.baseRegister != ldr2.destRegister)
 527       return;
 528     // Loads from the GOT must be pointer sized.
 529     if (ldr2.p2Size != 3 || ldr2.isFloat)
 530       return;
 531
 532     uint64_t addr1 = isec->getVA() + offset1;
 533     uint64_t addr2 = isec->getVA() + offset2;
 534     uint64_t referent = pageBits(addr1) + adrp.addend + ldr2.offset;
 535     // Load the GOT entry's address directly.
 536     //   nop
 537     //   ldr x2, _foo@GOTPAGE + _foo@GOTPAGEOFF
 538     //   ldr x3, [x2, #off]
 539     Ldr literalLdr = ldr2;
 540     literalLdr.offset = referent - addr2;
 541     if (isLiteralLdrEligible(literalLdr)) {
 542       writeNop(buf + offset1);
 543       writeLiteralLdr(buf + offset2, literalLdr);
 544     }
 545   }
 546 }
 547
 548 static uint64_t readValue(const uint8_t *&ptr, const uint8_t *end) {
 549   unsigned int n = 0;
 550   uint64_t value = decodeULEB128(ptr, &n, end);
 551   ptr += n;
 552   return value;
 553 }
 554
 555 template <typename Callback>
 556 static void forEachHint(ArrayRef<uint8_t> data, Callback callback) {
 557   std::array<uint64_t, 3> args;
 558
 559   for (const uint8_t *p = data.begin(), *end = data.end(); p < end;) {
 560     uint64_t type = readValue(p, end);
 561     if (type == 0)
 562       break;
 563
 564     uint64_t argCount = readValue(p, end);
 565     // All known LOH types as of 2022-09 have 3 or fewer arguments; skip others.
 566     if (argCount > 3) {
 567       for (unsigned i = 0; i < argCount; ++i)
 568         readValue(p, end);
 569       continue;
 570     }
 571
 572     for (unsigned i = 0; i < argCount; ++i)
 573       args[i] = readValue(p, end);
 574     callback(type, ArrayRef<uint64_t>(args.data(), argCount));
 575   }
 576 }
 577
 578 // On RISC architectures like arm64, materializing a memory address generally
 579 // takes multiple instructions. If the referenced symbol is located close enough
 580 // in memory, fewer instructions are needed.
 581 //
 582 // Linker optimization hints record where addresses are computed. After
 583 // addresses have been assigned, if possible, we change them to a shorter
 584 // sequence of instructions. The size of the binary is not modified; the
 585 // eliminated instructions are replaced with NOPs. This still leads to faster
 586 // code as the CPU can skip over NOPs quickly.
 587 //
 588 // LOHs are specified by the LC_LINKER_OPTIMIZATION_HINTS load command, which
 589 // points to a sequence of ULEB128-encoded numbers. Each entry specifies a
 590 // transformation kind, and 2 or 3 addresses where the instructions are located.
 591 void ARM64::applyOptimizationHints(uint8_t *outBuf, const ObjFile &obj) const {
 592   ArrayRef<uint8_t> data = obj.getOptimizationHints();
 593   if (data.empty())
 594     return;
 595
 596   const ConcatInputSection *section = nullptr;
 597   uint64_t sectionAddr = 0;
 598   uint8_t *buf = nullptr;
 599
 600   auto findSection = [&](uint64_t addr) {
 601     if (section && addr >= sectionAddr &&
 602         addr < sectionAddr + section->getSize())
 603       return true;
 604
 605     if (obj.sections.empty())
 606       return false;
 607     auto secIt = std::prev(llvm::upper_bound(
 608         obj.sections, addr,
 609         [](uint64_t off, const Section *sec) { return off < sec->addr; }));
 610     const Section *sec = *secIt;
 611
 612     if (sec->subsections.empty())
 613       return false;
 614     auto subsecIt = std::prev(llvm::upper_bound(
 615         sec->subsections, addr - sec->addr,
 616         [](uint64_t off, Subsection subsec) { return off < subsec.offset; }));
 617     const Subsection &subsec = *subsecIt;
 618     const ConcatInputSection *isec =
 619         dyn_cast_or_null<ConcatInputSection>(subsec.isec);
 620     if (!isec || isec->shouldOmitFromOutput())
 621       return false;
 622
 623     section = isec;
 624     sectionAddr = subsec.offset + sec->addr;
 625     buf = outBuf + section->outSecOff + section->parent->fileOff;
 626     return true;
 627   };
 628
 629   auto isValidOffset = [&](uint64_t offset) {
 630     if (offset < sectionAddr || offset >= sectionAddr + section->getSize()) {
 631       error(toString(&obj) +
 632             ": linker optimization hint spans multiple sections");
 633       return false;
 634     }
 635     return true;
 636   };
 637
 638   bool hasAdrpAdrp = false;
 639   forEachHint(data, [&](uint64_t kind, ArrayRef<uint64_t> args) {
 640     if (kind == LOH_ARM64_ADRP_ADRP) {
 641       hasAdrpAdrp = true;
 642       return;
 643     }
 644
 645     if (!findSection(args[0]))
 646       return;
 647     switch (kind) {
 648     case LOH_ARM64_ADRP_ADD:
 649       if (isValidOffset(args[1]))
 650         applyAdrpAdd(buf, section, args[0] - sectionAddr,
 651                      args[1] - sectionAddr);
 652       break;
 653     case LOH_ARM64_ADRP_LDR:
 654       if (isValidOffset(args[1]))
 655         applyAdrpLdr(buf, section, args[0] - sectionAddr,
 656                      args[1] - sectionAddr);
 657       break;
 658     case LOH_ARM64_ADRP_LDR_GOT:
 659       if (isValidOffset(args[1]))
 660         applyAdrpLdrGot(buf, section, args[0] - sectionAddr,
 661                         args[1] - sectionAddr);
 662       break;
 663     case LOH_ARM64_ADRP_ADD_LDR:
 664       if (isValidOffset(args[1]) && isValidOffset(args[2]))
 665         applyAdrpAddLdr(buf, section, args[0] - sectionAddr,
 666                         args[1] - sectionAddr, args[2] - sectionAddr);
 667       break;
 668     case LOH_ARM64_ADRP_LDR_GOT_LDR:
 669       if (isValidOffset(args[1]) && isValidOffset(args[2]))
 670         applyAdrpLdrGotLdr(buf, section, args[0] - sectionAddr,
 671                            args[1] - sectionAddr, args[2] - sectionAddr);
 672       break;
 673     case LOH_ARM64_ADRP_ADD_STR:
 674     case LOH_ARM64_ADRP_LDR_GOT_STR:
 675       // TODO: Implement these
 676       break;
 677     }
 678   });
 679
 680   if (!hasAdrpAdrp)
 681     return;
 682
 683   // AdrpAdrp optimization hints are performed in a second pass because they
 684   // might interfere with other transformations. For instance, consider the
 685   // following input:
 686   //
 687   //   adrp x0, _foo@PAGE
 688   //   add  x1, x0, _foo@PAGEOFF
 689   //   adrp x0, _bar@PAGE
 690   //   add  x2, x0, _bar@PAGEOFF
 691   //
 692   // If we perform the AdrpAdrp relaxation first, we get:
 693   //
 694   //   adrp x0, _foo@PAGE
 695   //   add  x1, x0, _foo@PAGEOFF
 696   //   nop
 697   //   add x2, x0, _bar@PAGEOFF
 698   //
 699   // If we then apply AdrpAdd to the first two instructions, the add will have a
 700   // garbage value in x0:
 701   //
 702   //   adr  x1, _foo
 703   //   nop
 704   //   nop
 705   //   add  x2, x0, _bar@PAGEOFF
 706   forEachHint(data, [&](uint64_t kind, ArrayRef<uint64_t> args) {
 707     if (kind != LOH_ARM64_ADRP_ADRP)
 708       return;
 709     if (!findSection(args[0]))
 710       return;
 711     if (isValidOffset(args[1]))
 712       applyAdrpAdrp(buf, section, args[0] - sectionAddr, args[1] - sectionAddr);
 713   });
 714 }
 715
 716 TargetInfo *macho::createARM64TargetInfo() {
 717   static ARM64 t;
 718   return &t;
 719 }