xref: /freebsd/contrib/llvm-project/lld/MachO/Arch/ARM64.cpp (revision 753f127f3ace09432b2baeffd71a308760641a62)
1fe6060f1SDimitry Andric //===- ARM64.cpp ----------------------------------------------------------===//
2fe6060f1SDimitry Andric //
3fe6060f1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4fe6060f1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5fe6060f1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6fe6060f1SDimitry Andric //
7fe6060f1SDimitry Andric //===----------------------------------------------------------------------===//
8fe6060f1SDimitry Andric 
9fe6060f1SDimitry Andric #include "Arch/ARM64Common.h"
10fe6060f1SDimitry Andric #include "InputFiles.h"
11fe6060f1SDimitry Andric #include "Symbols.h"
12fe6060f1SDimitry Andric #include "SyntheticSections.h"
13fe6060f1SDimitry Andric #include "Target.h"
14fe6060f1SDimitry Andric 
15fe6060f1SDimitry Andric #include "lld/Common/ErrorHandler.h"
1681ad6265SDimitry Andric #include "mach-o/compact_unwind_encoding.h"
17fe6060f1SDimitry Andric #include "llvm/ADT/SmallVector.h"
18fe6060f1SDimitry Andric #include "llvm/ADT/StringRef.h"
19fe6060f1SDimitry Andric #include "llvm/BinaryFormat/MachO.h"
20fe6060f1SDimitry Andric #include "llvm/Support/Endian.h"
21fe6060f1SDimitry Andric #include "llvm/Support/MathExtras.h"
22fe6060f1SDimitry Andric 
23fe6060f1SDimitry Andric using namespace llvm;
24fe6060f1SDimitry Andric using namespace llvm::MachO;
25fe6060f1SDimitry Andric using namespace llvm::support::endian;
26fe6060f1SDimitry Andric using namespace lld;
27fe6060f1SDimitry Andric using namespace lld::macho;
28fe6060f1SDimitry Andric 
29fe6060f1SDimitry Andric namespace {
30fe6060f1SDimitry Andric 
31fe6060f1SDimitry Andric struct ARM64 : ARM64Common {
32fe6060f1SDimitry Andric   ARM64();
33fe6060f1SDimitry Andric   void writeStub(uint8_t *buf, const Symbol &) const override;
34fe6060f1SDimitry Andric   void writeStubHelperHeader(uint8_t *buf) const override;
3581ad6265SDimitry Andric   void writeStubHelperEntry(uint8_t *buf, const Symbol &,
36fe6060f1SDimitry Andric                             uint64_t entryAddr) const override;
37fe6060f1SDimitry Andric   const RelocAttrs &getRelocAttrs(uint8_t type) const override;
38fe6060f1SDimitry Andric   void populateThunk(InputSection *thunk, Symbol *funcSym) override;
3981ad6265SDimitry Andric   void applyOptimizationHints(uint8_t *, const ConcatInputSection *,
4081ad6265SDimitry Andric                               ArrayRef<uint64_t>) const override;
41fe6060f1SDimitry Andric };
42fe6060f1SDimitry Andric 
43fe6060f1SDimitry Andric } // namespace
44fe6060f1SDimitry Andric 
45fe6060f1SDimitry Andric // Random notes on reloc types:
46fe6060f1SDimitry Andric // ADDEND always pairs with BRANCH26, PAGE21, or PAGEOFF12
47fe6060f1SDimitry Andric // POINTER_TO_GOT: ld64 supports a 4-byte pc-relative form as well as an 8-byte
48fe6060f1SDimitry Andric // absolute version of this relocation. The semantics of the absolute relocation
49fe6060f1SDimitry Andric // are weird -- it results in the value of the GOT slot being written, instead
50fe6060f1SDimitry Andric // of the address. Let's not support it unless we find a real-world use case.
51fe6060f1SDimitry Andric 
52fe6060f1SDimitry Andric const RelocAttrs &ARM64::getRelocAttrs(uint8_t type) const {
53fe6060f1SDimitry Andric   static const std::array<RelocAttrs, 11> relocAttrsArray{{
54fe6060f1SDimitry Andric #define B(x) RelocAttrBits::x
55fe6060f1SDimitry Andric       {"UNSIGNED",
56fe6060f1SDimitry Andric        B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
57fe6060f1SDimitry Andric       {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
58fe6060f1SDimitry Andric       {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
59fe6060f1SDimitry Andric       {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
60fe6060f1SDimitry Andric       {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
61fe6060f1SDimitry Andric       {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
62fe6060f1SDimitry Andric       {"GOT_LOAD_PAGEOFF12",
63fe6060f1SDimitry Andric        B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
64fe6060f1SDimitry Andric       {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
65fe6060f1SDimitry Andric       {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},
66fe6060f1SDimitry Andric       {"TLVP_LOAD_PAGEOFF12",
67fe6060f1SDimitry Andric        B(ABSOLUTE) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
68fe6060f1SDimitry Andric       {"ADDEND", B(ADDEND)},
69fe6060f1SDimitry Andric #undef B
70fe6060f1SDimitry Andric   }};
71fe6060f1SDimitry Andric   assert(type < relocAttrsArray.size() && "invalid relocation type");
72fe6060f1SDimitry Andric   if (type >= relocAttrsArray.size())
73fe6060f1SDimitry Andric     return invalidRelocAttrs;
74fe6060f1SDimitry Andric   return relocAttrsArray[type];
75fe6060f1SDimitry Andric }
76fe6060f1SDimitry Andric 
77fe6060f1SDimitry Andric static constexpr uint32_t stubCode[] = {
78fe6060f1SDimitry Andric     0x90000010, // 00: adrp  x16, __la_symbol_ptr@page
79fe6060f1SDimitry Andric     0xf9400210, // 04: ldr   x16, [x16, __la_symbol_ptr@pageoff]
80fe6060f1SDimitry Andric     0xd61f0200, // 08: br    x16
81fe6060f1SDimitry Andric };
82fe6060f1SDimitry Andric 
83fe6060f1SDimitry Andric void ARM64::writeStub(uint8_t *buf8, const Symbol &sym) const {
84fe6060f1SDimitry Andric   ::writeStub<LP64>(buf8, stubCode, sym);
85fe6060f1SDimitry Andric }
86fe6060f1SDimitry Andric 
87fe6060f1SDimitry Andric static constexpr uint32_t stubHelperHeaderCode[] = {
88fe6060f1SDimitry Andric     0x90000011, // 00: adrp  x17, _dyld_private@page
89fe6060f1SDimitry Andric     0x91000231, // 04: add   x17, x17, _dyld_private@pageoff
90fe6060f1SDimitry Andric     0xa9bf47f0, // 08: stp   x16/x17, [sp, #-16]!
91fe6060f1SDimitry Andric     0x90000010, // 0c: adrp  x16, dyld_stub_binder@page
92fe6060f1SDimitry Andric     0xf9400210, // 10: ldr   x16, [x16, dyld_stub_binder@pageoff]
93fe6060f1SDimitry Andric     0xd61f0200, // 14: br    x16
94fe6060f1SDimitry Andric };
95fe6060f1SDimitry Andric 
96fe6060f1SDimitry Andric void ARM64::writeStubHelperHeader(uint8_t *buf8) const {
97fe6060f1SDimitry Andric   ::writeStubHelperHeader<LP64>(buf8, stubHelperHeaderCode);
98fe6060f1SDimitry Andric }
99fe6060f1SDimitry Andric 
100fe6060f1SDimitry Andric static constexpr uint32_t stubHelperEntryCode[] = {
101fe6060f1SDimitry Andric     0x18000050, // 00: ldr  w16, l0
102fe6060f1SDimitry Andric     0x14000000, // 04: b    stubHelperHeader
103fe6060f1SDimitry Andric     0x00000000, // 08: l0: .long 0
104fe6060f1SDimitry Andric };
105fe6060f1SDimitry Andric 
10681ad6265SDimitry Andric void ARM64::writeStubHelperEntry(uint8_t *buf8, const Symbol &sym,
107fe6060f1SDimitry Andric                                  uint64_t entryVA) const {
108fe6060f1SDimitry Andric   ::writeStubHelperEntry(buf8, stubHelperEntryCode, sym, entryVA);
109fe6060f1SDimitry Andric }
110fe6060f1SDimitry Andric 
111fe6060f1SDimitry Andric // A thunk is the relaxed variation of stubCode. We don't need the
112fe6060f1SDimitry Andric // extra indirection through a lazy pointer because the target address
113fe6060f1SDimitry Andric // is known at link time.
114fe6060f1SDimitry Andric static constexpr uint32_t thunkCode[] = {
115fe6060f1SDimitry Andric     0x90000010, // 00: adrp  x16, <thunk.ptr>@page
116fe6060f1SDimitry Andric     0x91000210, // 04: add   x16, [x16,<thunk.ptr>@pageoff]
117fe6060f1SDimitry Andric     0xd61f0200, // 08: br    x16
118fe6060f1SDimitry Andric };
119fe6060f1SDimitry Andric 
120fe6060f1SDimitry Andric void ARM64::populateThunk(InputSection *thunk, Symbol *funcSym) {
121fe6060f1SDimitry Andric   thunk->align = 4;
122fe6060f1SDimitry Andric   thunk->data = {reinterpret_cast<const uint8_t *>(thunkCode),
123fe6060f1SDimitry Andric                  sizeof(thunkCode)};
124fe6060f1SDimitry Andric   thunk->relocs.push_back({/*type=*/ARM64_RELOC_PAGEOFF12,
125fe6060f1SDimitry Andric                            /*pcrel=*/false, /*length=*/2,
126fe6060f1SDimitry Andric                            /*offset=*/4, /*addend=*/0,
127fe6060f1SDimitry Andric                            /*referent=*/funcSym});
128fe6060f1SDimitry Andric   thunk->relocs.push_back({/*type=*/ARM64_RELOC_PAGE21,
129fe6060f1SDimitry Andric                            /*pcrel=*/true, /*length=*/2,
130fe6060f1SDimitry Andric                            /*offset=*/0, /*addend=*/0,
131fe6060f1SDimitry Andric                            /*referent=*/funcSym});
132fe6060f1SDimitry Andric }
133fe6060f1SDimitry Andric 
134fe6060f1SDimitry Andric ARM64::ARM64() : ARM64Common(LP64()) {
135fe6060f1SDimitry Andric   cpuType = CPU_TYPE_ARM64;
136fe6060f1SDimitry Andric   cpuSubtype = CPU_SUBTYPE_ARM64_ALL;
137fe6060f1SDimitry Andric 
138fe6060f1SDimitry Andric   stubSize = sizeof(stubCode);
139fe6060f1SDimitry Andric   thunkSize = sizeof(thunkCode);
140349cc55cSDimitry Andric 
141349cc55cSDimitry Andric   // Branch immediate is two's complement 26 bits, which is implicitly
142349cc55cSDimitry Andric   // multiplied by 4 (since all functions are 4-aligned: The branch range
143349cc55cSDimitry Andric   // is -4*(2**(26-1))..4*(2**(26-1) - 1).
144349cc55cSDimitry Andric   backwardBranchRange = 128 * 1024 * 1024;
145349cc55cSDimitry Andric   forwardBranchRange = backwardBranchRange - 4;
146349cc55cSDimitry Andric 
14781ad6265SDimitry Andric   modeDwarfEncoding = UNWIND_ARM64_MODE_DWARF;
14881ad6265SDimitry Andric   subtractorRelocType = ARM64_RELOC_SUBTRACTOR;
14981ad6265SDimitry Andric   unsignedRelocType = ARM64_RELOC_UNSIGNED;
15081ad6265SDimitry Andric 
151fe6060f1SDimitry Andric   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
152fe6060f1SDimitry Andric   stubHelperEntrySize = sizeof(stubHelperEntryCode);
153fe6060f1SDimitry Andric }
154fe6060f1SDimitry Andric 
15581ad6265SDimitry Andric namespace {
15681ad6265SDimitry Andric struct Adrp {
15781ad6265SDimitry Andric   uint32_t destRegister;
15881ad6265SDimitry Andric };
15981ad6265SDimitry Andric 
16081ad6265SDimitry Andric struct Add {
16181ad6265SDimitry Andric   uint8_t destRegister;
16281ad6265SDimitry Andric   uint8_t srcRegister;
16381ad6265SDimitry Andric   uint32_t addend;
16481ad6265SDimitry Andric };
16581ad6265SDimitry Andric 
16681ad6265SDimitry Andric enum ExtendType { ZeroExtend = 1, Sign64 = 2, Sign32 = 3 };
16781ad6265SDimitry Andric 
16881ad6265SDimitry Andric struct Ldr {
16981ad6265SDimitry Andric   uint8_t destRegister;
17081ad6265SDimitry Andric   uint8_t baseRegister;
171*753f127fSDimitry Andric   uint8_t p2Size;
17281ad6265SDimitry Andric   bool isFloat;
17381ad6265SDimitry Andric   ExtendType extendType;
174*753f127fSDimitry Andric   int64_t offset;
17581ad6265SDimitry Andric };
17681ad6265SDimitry Andric 
17781ad6265SDimitry Andric struct PerformedReloc {
17881ad6265SDimitry Andric   const Reloc &rel;
17981ad6265SDimitry Andric   uint64_t referentVA;
18081ad6265SDimitry Andric };
18181ad6265SDimitry Andric 
18281ad6265SDimitry Andric class OptimizationHintContext {
18381ad6265SDimitry Andric public:
18481ad6265SDimitry Andric   OptimizationHintContext(uint8_t *buf, const ConcatInputSection *isec,
18581ad6265SDimitry Andric                           ArrayRef<uint64_t> relocTargets)
18681ad6265SDimitry Andric       : buf(buf), isec(isec), relocTargets(relocTargets),
18781ad6265SDimitry Andric         relocIt(isec->relocs.rbegin()) {}
18881ad6265SDimitry Andric 
18981ad6265SDimitry Andric   void applyAdrpAdd(const OptimizationHint &);
19081ad6265SDimitry Andric   void applyAdrpAdrp(const OptimizationHint &);
19181ad6265SDimitry Andric   void applyAdrpLdr(const OptimizationHint &);
192*753f127fSDimitry Andric   void applyAdrpLdrGot(const OptimizationHint &);
193*753f127fSDimitry Andric   void applyAdrpLdrGotLdr(const OptimizationHint &);
19481ad6265SDimitry Andric 
19581ad6265SDimitry Andric private:
19681ad6265SDimitry Andric   uint8_t *buf;
19781ad6265SDimitry Andric   const ConcatInputSection *isec;
19881ad6265SDimitry Andric   ArrayRef<uint64_t> relocTargets;
19981ad6265SDimitry Andric   std::vector<Reloc>::const_reverse_iterator relocIt;
20081ad6265SDimitry Andric 
20181ad6265SDimitry Andric   uint64_t getRelocTarget(const Reloc &);
20281ad6265SDimitry Andric 
20381ad6265SDimitry Andric   Optional<PerformedReloc> findPrimaryReloc(uint64_t offset);
20481ad6265SDimitry Andric   Optional<PerformedReloc> findReloc(uint64_t offset);
20581ad6265SDimitry Andric };
20681ad6265SDimitry Andric } // namespace
20781ad6265SDimitry Andric 
20881ad6265SDimitry Andric static bool parseAdrp(uint32_t insn, Adrp &adrp) {
20981ad6265SDimitry Andric   if ((insn & 0x9f000000) != 0x90000000)
21081ad6265SDimitry Andric     return false;
21181ad6265SDimitry Andric   adrp.destRegister = insn & 0x1f;
21281ad6265SDimitry Andric   return true;
21381ad6265SDimitry Andric }
21481ad6265SDimitry Andric 
21581ad6265SDimitry Andric static bool parseAdd(uint32_t insn, Add &add) {
21681ad6265SDimitry Andric   if ((insn & 0xffc00000) != 0x91000000)
21781ad6265SDimitry Andric     return false;
21881ad6265SDimitry Andric   add.destRegister = insn & 0x1f;
21981ad6265SDimitry Andric   add.srcRegister = (insn >> 5) & 0x1f;
22081ad6265SDimitry Andric   add.addend = (insn >> 10) & 0xfff;
22181ad6265SDimitry Andric   return true;
22281ad6265SDimitry Andric }
22381ad6265SDimitry Andric 
22481ad6265SDimitry Andric static bool parseLdr(uint32_t insn, Ldr &ldr) {
22581ad6265SDimitry Andric   ldr.destRegister = insn & 0x1f;
22681ad6265SDimitry Andric   ldr.baseRegister = (insn >> 5) & 0x1f;
22781ad6265SDimitry Andric   uint8_t size = insn >> 30;
22881ad6265SDimitry Andric   uint8_t opc = (insn >> 22) & 3;
22981ad6265SDimitry Andric 
23081ad6265SDimitry Andric   if ((insn & 0x3fc00000) == 0x39400000) {
23181ad6265SDimitry Andric     // LDR (immediate), LDRB (immediate), LDRH (immediate)
232*753f127fSDimitry Andric     ldr.p2Size = size;
23381ad6265SDimitry Andric     ldr.extendType = ZeroExtend;
23481ad6265SDimitry Andric     ldr.isFloat = false;
23581ad6265SDimitry Andric   } else if ((insn & 0x3f800000) == 0x39800000) {
23681ad6265SDimitry Andric     // LDRSB (immediate), LDRSH (immediate), LDRSW (immediate)
237*753f127fSDimitry Andric     ldr.p2Size = size;
23881ad6265SDimitry Andric     ldr.extendType = static_cast<ExtendType>(opc);
23981ad6265SDimitry Andric     ldr.isFloat = false;
24081ad6265SDimitry Andric   } else if ((insn & 0x3f400000) == 0x3d400000) {
24181ad6265SDimitry Andric     // LDR (immediate, SIMD&FP)
24281ad6265SDimitry Andric     ldr.extendType = ZeroExtend;
24381ad6265SDimitry Andric     ldr.isFloat = true;
244*753f127fSDimitry Andric     if (opc == 1)
245*753f127fSDimitry Andric       ldr.p2Size = size;
24681ad6265SDimitry Andric     else if (size == 0 && opc == 3)
247*753f127fSDimitry Andric       ldr.p2Size = 4;
24881ad6265SDimitry Andric     else
24981ad6265SDimitry Andric       return false;
25081ad6265SDimitry Andric   } else {
25181ad6265SDimitry Andric     return false;
25281ad6265SDimitry Andric   }
253*753f127fSDimitry Andric   ldr.offset = ((insn >> 10) & 0xfff) << ldr.p2Size;
25481ad6265SDimitry Andric   return true;
25581ad6265SDimitry Andric }
25681ad6265SDimitry Andric 
257*753f127fSDimitry Andric static bool isValidAdrOffset(int32_t delta) { return isInt<21>(delta); }
258*753f127fSDimitry Andric 
25981ad6265SDimitry Andric static void writeAdr(void *loc, uint32_t dest, int32_t delta) {
260*753f127fSDimitry Andric   assert(isValidAdrOffset(delta));
26181ad6265SDimitry Andric   uint32_t opcode = 0x10000000;
26281ad6265SDimitry Andric   uint32_t immHi = (delta & 0x001ffffc) << 3;
26381ad6265SDimitry Andric   uint32_t immLo = (delta & 0x00000003) << 29;
26481ad6265SDimitry Andric   write32le(loc, opcode | immHi | immLo | dest);
26581ad6265SDimitry Andric }
26681ad6265SDimitry Andric 
26781ad6265SDimitry Andric static void writeNop(void *loc) { write32le(loc, 0xd503201f); }
26881ad6265SDimitry Andric 
269*753f127fSDimitry Andric static bool isLiteralLdrEligible(const Ldr &ldr) {
270*753f127fSDimitry Andric   return ldr.p2Size > 1 && isShiftedInt<19, 2>(ldr.offset);
271*753f127fSDimitry Andric }
272*753f127fSDimitry Andric 
273*753f127fSDimitry Andric static void writeLiteralLdr(void *loc, const Ldr &ldr) {
274*753f127fSDimitry Andric   assert(isLiteralLdrEligible(ldr));
275*753f127fSDimitry Andric   uint32_t imm19 = (ldr.offset / 4 & maskTrailingOnes<uint32_t>(19)) << 5;
276*753f127fSDimitry Andric   uint32_t opcode;
277*753f127fSDimitry Andric   switch (ldr.p2Size) {
278*753f127fSDimitry Andric   case 2:
279*753f127fSDimitry Andric     if (ldr.isFloat)
28081ad6265SDimitry Andric       opcode = 0x1c000000;
28181ad6265SDimitry Andric     else
282*753f127fSDimitry Andric       opcode = ldr.extendType == Sign64 ? 0x98000000 : 0x18000000;
28381ad6265SDimitry Andric     break;
284*753f127fSDimitry Andric   case 3:
285*753f127fSDimitry Andric     opcode = ldr.isFloat ? 0x5c000000 : 0x58000000;
28681ad6265SDimitry Andric     break;
287*753f127fSDimitry Andric   case 4:
28881ad6265SDimitry Andric     opcode = 0x9c000000;
28981ad6265SDimitry Andric     break;
29081ad6265SDimitry Andric   default:
291*753f127fSDimitry Andric     llvm_unreachable("Invalid literal ldr size");
29281ad6265SDimitry Andric   }
293*753f127fSDimitry Andric   write32le(loc, opcode | imm19 | ldr.destRegister);
294*753f127fSDimitry Andric }
295*753f127fSDimitry Andric 
296*753f127fSDimitry Andric static bool isImmediateLdrEligible(const Ldr &ldr) {
297*753f127fSDimitry Andric   // Note: We deviate from ld64's behavior, which converts to immediate loads
298*753f127fSDimitry Andric   // only if ldr.offset < 4096, even though the offset is divided by the load's
299*753f127fSDimitry Andric   // size in the 12-bit immediate operand. Only the unsigned offset variant is
300*753f127fSDimitry Andric   // supported.
301*753f127fSDimitry Andric 
302*753f127fSDimitry Andric   uint32_t size = 1 << ldr.p2Size;
303*753f127fSDimitry Andric   return ldr.offset >= 0 && (ldr.offset % size) == 0 &&
304*753f127fSDimitry Andric          isUInt<12>(ldr.offset >> ldr.p2Size);
305*753f127fSDimitry Andric }
306*753f127fSDimitry Andric 
307*753f127fSDimitry Andric static void writeImmediateLdr(void *loc, const Ldr &ldr) {
308*753f127fSDimitry Andric   assert(isImmediateLdrEligible(ldr));
309*753f127fSDimitry Andric   uint32_t opcode = 0x39000000;
310*753f127fSDimitry Andric   if (ldr.isFloat) {
311*753f127fSDimitry Andric     opcode |= 0x04000000;
312*753f127fSDimitry Andric     assert(ldr.extendType == ZeroExtend);
313*753f127fSDimitry Andric   }
314*753f127fSDimitry Andric   opcode |= ldr.destRegister;
315*753f127fSDimitry Andric   opcode |= ldr.baseRegister << 5;
316*753f127fSDimitry Andric   uint8_t size, opc;
317*753f127fSDimitry Andric   if (ldr.p2Size == 4) {
318*753f127fSDimitry Andric     size = 0;
319*753f127fSDimitry Andric     opc = 3;
320*753f127fSDimitry Andric   } else {
321*753f127fSDimitry Andric     opc = ldr.extendType;
322*753f127fSDimitry Andric     size = ldr.p2Size;
323*753f127fSDimitry Andric   }
324*753f127fSDimitry Andric   uint32_t immBits = ldr.offset >> ldr.p2Size;
325*753f127fSDimitry Andric   write32le(loc, opcode | (immBits << 10) | (opc << 22) | (size << 30));
32681ad6265SDimitry Andric }
32781ad6265SDimitry Andric 
32881ad6265SDimitry Andric uint64_t OptimizationHintContext::getRelocTarget(const Reloc &reloc) {
32981ad6265SDimitry Andric   size_t relocIdx = &reloc - isec->relocs.data();
33081ad6265SDimitry Andric   return relocTargets[relocIdx];
33181ad6265SDimitry Andric }
33281ad6265SDimitry Andric 
33381ad6265SDimitry Andric // Optimization hints are sorted in a monotonically increasing order by their
33481ad6265SDimitry Andric // first address as are relocations (albeit in decreasing order), so if we keep
33581ad6265SDimitry Andric // a pointer around to the last found relocation, we don't have to do a full
33681ad6265SDimitry Andric // binary search every time.
33781ad6265SDimitry Andric Optional<PerformedReloc>
33881ad6265SDimitry Andric OptimizationHintContext::findPrimaryReloc(uint64_t offset) {
33981ad6265SDimitry Andric   const auto end = isec->relocs.rend();
34081ad6265SDimitry Andric   while (relocIt != end && relocIt->offset < offset)
34181ad6265SDimitry Andric     ++relocIt;
34281ad6265SDimitry Andric   if (relocIt == end || relocIt->offset != offset)
34381ad6265SDimitry Andric     return None;
34481ad6265SDimitry Andric   return PerformedReloc{*relocIt, getRelocTarget(*relocIt)};
34581ad6265SDimitry Andric }
34681ad6265SDimitry Andric 
34781ad6265SDimitry Andric // The second and third addresses of optimization hints have no such
34881ad6265SDimitry Andric // monotonicity as the first, so we search the entire range of relocations.
34981ad6265SDimitry Andric Optional<PerformedReloc> OptimizationHintContext::findReloc(uint64_t offset) {
35081ad6265SDimitry Andric   // Optimization hints often apply to successive relocations, so we check for
35181ad6265SDimitry Andric   // that first before doing a full binary search.
35281ad6265SDimitry Andric   auto end = isec->relocs.rend();
35381ad6265SDimitry Andric   if (relocIt < end - 1 && (relocIt + 1)->offset == offset)
35481ad6265SDimitry Andric     return PerformedReloc{*(relocIt + 1), getRelocTarget(*(relocIt + 1))};
35581ad6265SDimitry Andric 
35681ad6265SDimitry Andric   auto reloc = lower_bound(isec->relocs, offset,
35781ad6265SDimitry Andric                            [](const Reloc &reloc, uint64_t offset) {
35881ad6265SDimitry Andric                              return offset < reloc.offset;
35981ad6265SDimitry Andric                            });
36081ad6265SDimitry Andric 
36181ad6265SDimitry Andric   if (reloc == isec->relocs.end() || reloc->offset != offset)
36281ad6265SDimitry Andric     return None;
36381ad6265SDimitry Andric   return PerformedReloc{*reloc, getRelocTarget(*reloc)};
36481ad6265SDimitry Andric }
36581ad6265SDimitry Andric 
36681ad6265SDimitry Andric // Transforms a pair of adrp+add instructions into an adr instruction if the
36781ad6265SDimitry Andric // target is within the +/- 1 MiB range allowed by the adr's 21 bit signed
36881ad6265SDimitry Andric // immediate offset.
36981ad6265SDimitry Andric //
37081ad6265SDimitry Andric //   adrp xN, _foo@PAGE
37181ad6265SDimitry Andric //   add  xM, xN, _foo@PAGEOFF
37281ad6265SDimitry Andric // ->
37381ad6265SDimitry Andric //   adr  xM, _foo
37481ad6265SDimitry Andric //   nop
37581ad6265SDimitry Andric void OptimizationHintContext::applyAdrpAdd(const OptimizationHint &hint) {
37681ad6265SDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
37781ad6265SDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
37881ad6265SDimitry Andric   Adrp adrp;
37981ad6265SDimitry Andric   if (!parseAdrp(ins1, adrp))
38081ad6265SDimitry Andric     return;
38181ad6265SDimitry Andric   Add add;
38281ad6265SDimitry Andric   if (!parseAdd(ins2, add))
38381ad6265SDimitry Andric     return;
38481ad6265SDimitry Andric   if (adrp.destRegister != add.srcRegister)
38581ad6265SDimitry Andric     return;
38681ad6265SDimitry Andric 
38781ad6265SDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
38881ad6265SDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
38981ad6265SDimitry Andric   if (!rel1 || !rel2)
39081ad6265SDimitry Andric     return;
39181ad6265SDimitry Andric   if (rel1->referentVA != rel2->referentVA)
39281ad6265SDimitry Andric     return;
39381ad6265SDimitry Andric   int64_t delta = rel1->referentVA - rel1->rel.offset - isec->getVA();
394*753f127fSDimitry Andric   if (!isValidAdrOffset(delta))
39581ad6265SDimitry Andric     return;
39681ad6265SDimitry Andric 
39781ad6265SDimitry Andric   writeAdr(buf + hint.offset0, add.destRegister, delta);
39881ad6265SDimitry Andric   writeNop(buf + hint.offset0 + hint.delta[0]);
39981ad6265SDimitry Andric }
40081ad6265SDimitry Andric 
40181ad6265SDimitry Andric // Transforms two adrp instructions into a single adrp if their referent
40281ad6265SDimitry Andric // addresses are located on the same 4096 byte page.
40381ad6265SDimitry Andric //
40481ad6265SDimitry Andric //   adrp xN, _foo@PAGE
40581ad6265SDimitry Andric //   adrp xN, _bar@PAGE
40681ad6265SDimitry Andric // ->
40781ad6265SDimitry Andric //   adrp xN, _foo@PAGE
40881ad6265SDimitry Andric //   nop
40981ad6265SDimitry Andric void OptimizationHintContext::applyAdrpAdrp(const OptimizationHint &hint) {
41081ad6265SDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
41181ad6265SDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
41281ad6265SDimitry Andric   Adrp adrp1, adrp2;
41381ad6265SDimitry Andric   if (!parseAdrp(ins1, adrp1) || !parseAdrp(ins2, adrp2))
41481ad6265SDimitry Andric     return;
41581ad6265SDimitry Andric   if (adrp1.destRegister != adrp2.destRegister)
41681ad6265SDimitry Andric     return;
41781ad6265SDimitry Andric 
41881ad6265SDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
41981ad6265SDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
42081ad6265SDimitry Andric   if (!rel1 || !rel2)
42181ad6265SDimitry Andric     return;
42281ad6265SDimitry Andric   if ((rel1->referentVA & ~0xfffULL) != (rel2->referentVA & ~0xfffULL))
42381ad6265SDimitry Andric     return;
42481ad6265SDimitry Andric 
42581ad6265SDimitry Andric   writeNop(buf + hint.offset0 + hint.delta[0]);
42681ad6265SDimitry Andric }
42781ad6265SDimitry Andric 
42881ad6265SDimitry Andric // Transforms a pair of adrp+ldr (immediate) instructions into an ldr (literal)
42981ad6265SDimitry Andric // load from a PC-relative address if it is 4-byte aligned and within +/- 1 MiB,
43081ad6265SDimitry Andric // as ldr can encode a signed 19-bit offset that gets multiplied by 4.
43181ad6265SDimitry Andric //
43281ad6265SDimitry Andric //   adrp xN, _foo@PAGE
43381ad6265SDimitry Andric //   ldr  xM, [xN, _foo@PAGEOFF]
43481ad6265SDimitry Andric // ->
43581ad6265SDimitry Andric //   nop
43681ad6265SDimitry Andric //   ldr  xM, _foo
43781ad6265SDimitry Andric void OptimizationHintContext::applyAdrpLdr(const OptimizationHint &hint) {
43881ad6265SDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
43981ad6265SDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
44081ad6265SDimitry Andric   Adrp adrp;
44181ad6265SDimitry Andric   if (!parseAdrp(ins1, adrp))
44281ad6265SDimitry Andric     return;
44381ad6265SDimitry Andric   Ldr ldr;
44481ad6265SDimitry Andric   if (!parseLdr(ins2, ldr))
44581ad6265SDimitry Andric     return;
44681ad6265SDimitry Andric   if (adrp.destRegister != ldr.baseRegister)
44781ad6265SDimitry Andric     return;
44881ad6265SDimitry Andric 
44981ad6265SDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
45081ad6265SDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
45181ad6265SDimitry Andric   if (!rel1 || !rel2)
45281ad6265SDimitry Andric     return;
45381ad6265SDimitry Andric   if (ldr.offset != (rel1->referentVA & 0xfff))
45481ad6265SDimitry Andric     return;
455*753f127fSDimitry Andric   ldr.offset = rel1->referentVA - rel2->rel.offset - isec->getVA();
456*753f127fSDimitry Andric   if (!isLiteralLdrEligible(ldr))
45781ad6265SDimitry Andric     return;
45881ad6265SDimitry Andric 
45981ad6265SDimitry Andric   writeNop(buf + hint.offset0);
460*753f127fSDimitry Andric   writeLiteralLdr(buf + hint.offset0 + hint.delta[0], ldr);
461*753f127fSDimitry Andric }
462*753f127fSDimitry Andric 
463*753f127fSDimitry Andric // GOT loads are emitted by the compiler as a pair of adrp and ldr instructions,
464*753f127fSDimitry Andric // but they may be changed to adrp+add by relaxGotLoad(). This hint performs
465*753f127fSDimitry Andric // the AdrpLdr or AdrpAdd transformation depending on whether it was relaxed.
466*753f127fSDimitry Andric void OptimizationHintContext::applyAdrpLdrGot(const OptimizationHint &hint) {
467*753f127fSDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
468*753f127fSDimitry Andric   Add add;
469*753f127fSDimitry Andric   Ldr ldr;
470*753f127fSDimitry Andric   if (parseAdd(ins2, add))
471*753f127fSDimitry Andric     applyAdrpAdd(hint);
472*753f127fSDimitry Andric   else if (parseLdr(ins2, ldr))
473*753f127fSDimitry Andric     applyAdrpLdr(hint);
474*753f127fSDimitry Andric }
475*753f127fSDimitry Andric 
476*753f127fSDimitry Andric // Relaxes a GOT-indirect load.
477*753f127fSDimitry Andric // If the referenced symbol is external and its GOT entry is within +/- 1 MiB,
478*753f127fSDimitry Andric // the GOT entry can be loaded with a single literal ldr instruction.
479*753f127fSDimitry Andric // If the referenced symbol is local, its address may be loaded directly if it's
480*753f127fSDimitry Andric // close enough, or with an adr(p) + ldr pair if it's not.
481*753f127fSDimitry Andric void OptimizationHintContext::applyAdrpLdrGotLdr(const OptimizationHint &hint) {
482*753f127fSDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
483*753f127fSDimitry Andric   Adrp adrp;
484*753f127fSDimitry Andric   if (!parseAdrp(ins1, adrp))
485*753f127fSDimitry Andric     return;
486*753f127fSDimitry Andric   uint32_t ins3 = read32le(buf + hint.offset0 + hint.delta[1]);
487*753f127fSDimitry Andric   Ldr ldr3;
488*753f127fSDimitry Andric   if (!parseLdr(ins3, ldr3))
489*753f127fSDimitry Andric     return;
490*753f127fSDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
491*753f127fSDimitry Andric   Ldr ldr2;
492*753f127fSDimitry Andric   Add add2;
493*753f127fSDimitry Andric 
494*753f127fSDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
495*753f127fSDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
496*753f127fSDimitry Andric   if (!rel1 || !rel2)
497*753f127fSDimitry Andric     return;
498*753f127fSDimitry Andric 
499*753f127fSDimitry Andric   if (parseAdd(ins2, add2)) {
500*753f127fSDimitry Andric     // adrp x0, _foo@PAGE
501*753f127fSDimitry Andric     // add  x1, x0, _foo@PAGEOFF
502*753f127fSDimitry Andric     // ldr  x2, [x1, #off]
503*753f127fSDimitry Andric 
504*753f127fSDimitry Andric     if (adrp.destRegister != add2.srcRegister)
505*753f127fSDimitry Andric       return;
506*753f127fSDimitry Andric     if (add2.destRegister != ldr3.baseRegister)
507*753f127fSDimitry Andric       return;
508*753f127fSDimitry Andric 
509*753f127fSDimitry Andric     // Load from the target address directly.
510*753f127fSDimitry Andric     //   nop
511*753f127fSDimitry Andric     //   nop
512*753f127fSDimitry Andric     //   ldr x2, [_foo + #off]
513*753f127fSDimitry Andric     uint64_t rel3VA = hint.offset0 + hint.delta[1] + isec->getVA();
514*753f127fSDimitry Andric     Ldr literalLdr = ldr3;
515*753f127fSDimitry Andric     literalLdr.offset += rel1->referentVA - rel3VA;
516*753f127fSDimitry Andric     if (isLiteralLdrEligible(literalLdr)) {
517*753f127fSDimitry Andric       writeNop(buf + hint.offset0);
518*753f127fSDimitry Andric       writeNop(buf + hint.offset0 + hint.delta[0]);
519*753f127fSDimitry Andric       writeLiteralLdr(buf + hint.offset0 + hint.delta[1], literalLdr);
520*753f127fSDimitry Andric       return;
521*753f127fSDimitry Andric     }
522*753f127fSDimitry Andric 
523*753f127fSDimitry Andric     // Load the target address into a register and load from there indirectly.
524*753f127fSDimitry Andric     //   adr x1, _foo
525*753f127fSDimitry Andric     //   nop
526*753f127fSDimitry Andric     //   ldr x2, [x1, #off]
527*753f127fSDimitry Andric     int64_t adrOffset = rel1->referentVA - rel1->rel.offset - isec->getVA();
528*753f127fSDimitry Andric     if (isValidAdrOffset(adrOffset)) {
529*753f127fSDimitry Andric       writeAdr(buf + hint.offset0, ldr3.baseRegister, adrOffset);
530*753f127fSDimitry Andric       writeNop(buf + hint.offset0 + hint.delta[0]);
531*753f127fSDimitry Andric       return;
532*753f127fSDimitry Andric     }
533*753f127fSDimitry Andric 
534*753f127fSDimitry Andric     // Move the target's page offset into the ldr's immediate offset.
535*753f127fSDimitry Andric     //   adrp x0, _foo@PAGE
536*753f127fSDimitry Andric     //   nop
537*753f127fSDimitry Andric     //   ldr x2, [x0, _foo@PAGEOFF + #off]
538*753f127fSDimitry Andric     Ldr immediateLdr = ldr3;
539*753f127fSDimitry Andric     immediateLdr.baseRegister = adrp.destRegister;
540*753f127fSDimitry Andric     immediateLdr.offset += add2.addend;
541*753f127fSDimitry Andric     if (isImmediateLdrEligible(immediateLdr)) {
542*753f127fSDimitry Andric       writeNop(buf + hint.offset0 + hint.delta[0]);
543*753f127fSDimitry Andric       writeImmediateLdr(buf + hint.offset0 + hint.delta[1], immediateLdr);
544*753f127fSDimitry Andric       return;
545*753f127fSDimitry Andric     }
546*753f127fSDimitry Andric   } else if (parseLdr(ins2, ldr2)) {
547*753f127fSDimitry Andric     // adrp x1, _foo@GOTPAGE
548*753f127fSDimitry Andric     // ldr  x2, [x1, _foo@GOTPAGEOFF]
549*753f127fSDimitry Andric     // ldr  x3, [x2, #off]
550*753f127fSDimitry Andric     if (ldr2.baseRegister != adrp.destRegister)
551*753f127fSDimitry Andric       return;
552*753f127fSDimitry Andric     if (ldr3.baseRegister != ldr2.destRegister)
553*753f127fSDimitry Andric       return;
554*753f127fSDimitry Andric     // Loads from the GOT must be pointer sized.
555*753f127fSDimitry Andric     if (ldr2.p2Size != 3 || ldr2.isFloat)
556*753f127fSDimitry Andric       return;
557*753f127fSDimitry Andric 
558*753f127fSDimitry Andric     // Load the GOT entry's address directly.
559*753f127fSDimitry Andric     //   nop
560*753f127fSDimitry Andric     //   ldr x2, _foo@GOTPAGE + _foo@GOTPAGEOFF
561*753f127fSDimitry Andric     //   ldr x3, [x2, #off]
562*753f127fSDimitry Andric     Ldr literalLdr = ldr2;
563*753f127fSDimitry Andric     literalLdr.offset = rel1->referentVA - rel2->rel.offset - isec->getVA();
564*753f127fSDimitry Andric     if (isLiteralLdrEligible(literalLdr)) {
565*753f127fSDimitry Andric       writeNop(buf + hint.offset0);
566*753f127fSDimitry Andric       writeLiteralLdr(buf + hint.offset0 + hint.delta[0], literalLdr);
567*753f127fSDimitry Andric     }
568*753f127fSDimitry Andric   }
56981ad6265SDimitry Andric }
57081ad6265SDimitry Andric 
57181ad6265SDimitry Andric void ARM64::applyOptimizationHints(uint8_t *buf, const ConcatInputSection *isec,
57281ad6265SDimitry Andric                                    ArrayRef<uint64_t> relocTargets) const {
57381ad6265SDimitry Andric   assert(isec);
57481ad6265SDimitry Andric   assert(relocTargets.size() == isec->relocs.size());
57581ad6265SDimitry Andric 
57681ad6265SDimitry Andric   // Note: Some of these optimizations might not be valid when shared regions
57781ad6265SDimitry Andric   // are in use. Will need to revisit this if splitSegInfo is added.
57881ad6265SDimitry Andric 
57981ad6265SDimitry Andric   OptimizationHintContext ctx1(buf, isec, relocTargets);
58081ad6265SDimitry Andric   for (const OptimizationHint &hint : isec->optimizationHints) {
58181ad6265SDimitry Andric     switch (hint.type) {
58281ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADRP:
58381ad6265SDimitry Andric       // This is done in another pass because the other optimization hints
58481ad6265SDimitry Andric       // might cause its targets to be turned into NOPs.
58581ad6265SDimitry Andric       break;
58681ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR:
58781ad6265SDimitry Andric       ctx1.applyAdrpLdr(hint);
58881ad6265SDimitry Andric       break;
58981ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADD_LDR:
590*753f127fSDimitry Andric       // TODO: Implement this
591*753f127fSDimitry Andric       break;
59281ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR_GOT_LDR:
593*753f127fSDimitry Andric       ctx1.applyAdrpLdrGotLdr(hint);
594*753f127fSDimitry Andric       break;
59581ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADD_STR:
59681ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR_GOT_STR:
59781ad6265SDimitry Andric       // TODO: Implement these
59881ad6265SDimitry Andric       break;
59981ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADD:
60081ad6265SDimitry Andric       ctx1.applyAdrpAdd(hint);
60181ad6265SDimitry Andric       break;
60281ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR_GOT:
603*753f127fSDimitry Andric       ctx1.applyAdrpLdrGot(hint);
60481ad6265SDimitry Andric       break;
60581ad6265SDimitry Andric     }
60681ad6265SDimitry Andric   }
60781ad6265SDimitry Andric 
60881ad6265SDimitry Andric   OptimizationHintContext ctx2(buf, isec, relocTargets);
60981ad6265SDimitry Andric   for (const OptimizationHint &hint : isec->optimizationHints)
61081ad6265SDimitry Andric     if (hint.type == LOH_ARM64_ADRP_ADRP)
61181ad6265SDimitry Andric       ctx2.applyAdrpAdrp(hint);
61281ad6265SDimitry Andric }
61381ad6265SDimitry Andric 
614fe6060f1SDimitry Andric TargetInfo *macho::createARM64TargetInfo() {
615fe6060f1SDimitry Andric   static ARM64 t;
616fe6060f1SDimitry Andric   return &t;
617fe6060f1SDimitry Andric }
618