xref: /freebsd/contrib/llvm-project/lld/MachO/Arch/ARM64.cpp (revision fcaf7f8644a9988098ac6be2165bce3ea4786e91)
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   void populateThunk(InputSection *thunk, Symbol *funcSym) override;
3881ad6265SDimitry Andric   void applyOptimizationHints(uint8_t *, const ConcatInputSection *,
3981ad6265SDimitry Andric                               ArrayRef<uint64_t>) const override;
40fe6060f1SDimitry Andric };
41fe6060f1SDimitry Andric 
42fe6060f1SDimitry Andric } // namespace
43fe6060f1SDimitry Andric 
44fe6060f1SDimitry Andric // Random notes on reloc types:
45fe6060f1SDimitry Andric // ADDEND always pairs with BRANCH26, PAGE21, or PAGEOFF12
46fe6060f1SDimitry Andric // POINTER_TO_GOT: ld64 supports a 4-byte pc-relative form as well as an 8-byte
47fe6060f1SDimitry Andric // absolute version of this relocation. The semantics of the absolute relocation
48fe6060f1SDimitry Andric // are weird -- it results in the value of the GOT slot being written, instead
49fe6060f1SDimitry Andric // of the address. Let's not support it unless we find a real-world use case.
50*fcaf7f86SDimitry Andric static constexpr std::array<RelocAttrs, 11> relocAttrsArray{{
51fe6060f1SDimitry Andric #define B(x) RelocAttrBits::x
52fe6060f1SDimitry Andric     {"UNSIGNED",
53fe6060f1SDimitry Andric      B(UNSIGNED) | B(ABSOLUTE) | B(EXTERN) | B(LOCAL) | B(BYTE4) | B(BYTE8)},
54fe6060f1SDimitry Andric     {"SUBTRACTOR", B(SUBTRAHEND) | B(EXTERN) | B(BYTE4) | B(BYTE8)},
55fe6060f1SDimitry Andric     {"BRANCH26", B(PCREL) | B(EXTERN) | B(BRANCH) | B(BYTE4)},
56fe6060f1SDimitry Andric     {"PAGE21", B(PCREL) | B(EXTERN) | B(BYTE4)},
57fe6060f1SDimitry Andric     {"PAGEOFF12", B(ABSOLUTE) | B(EXTERN) | B(BYTE4)},
58fe6060f1SDimitry Andric     {"GOT_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(GOT) | B(BYTE4)},
59fe6060f1SDimitry Andric     {"GOT_LOAD_PAGEOFF12",
60fe6060f1SDimitry Andric      B(ABSOLUTE) | B(EXTERN) | B(GOT) | B(LOAD) | B(BYTE4)},
61fe6060f1SDimitry Andric     {"POINTER_TO_GOT", B(PCREL) | B(EXTERN) | B(GOT) | B(POINTER) | B(BYTE4)},
62fe6060f1SDimitry Andric     {"TLVP_LOAD_PAGE21", B(PCREL) | B(EXTERN) | B(TLV) | B(BYTE4)},
63fe6060f1SDimitry Andric     {"TLVP_LOAD_PAGEOFF12",
64fe6060f1SDimitry Andric      B(ABSOLUTE) | B(EXTERN) | B(TLV) | B(LOAD) | B(BYTE4)},
65fe6060f1SDimitry Andric     {"ADDEND", B(ADDEND)},
66fe6060f1SDimitry Andric #undef B
67fe6060f1SDimitry Andric }};
68fe6060f1SDimitry Andric 
69fe6060f1SDimitry Andric static constexpr uint32_t stubCode[] = {
70fe6060f1SDimitry Andric     0x90000010, // 00: adrp  x16, __la_symbol_ptr@page
71fe6060f1SDimitry Andric     0xf9400210, // 04: ldr   x16, [x16, __la_symbol_ptr@pageoff]
72fe6060f1SDimitry Andric     0xd61f0200, // 08: br    x16
73fe6060f1SDimitry Andric };
74fe6060f1SDimitry Andric 
75fe6060f1SDimitry Andric void ARM64::writeStub(uint8_t *buf8, const Symbol &sym) const {
76fe6060f1SDimitry Andric   ::writeStub<LP64>(buf8, stubCode, sym);
77fe6060f1SDimitry Andric }
78fe6060f1SDimitry Andric 
79fe6060f1SDimitry Andric static constexpr uint32_t stubHelperHeaderCode[] = {
80fe6060f1SDimitry Andric     0x90000011, // 00: adrp  x17, _dyld_private@page
81fe6060f1SDimitry Andric     0x91000231, // 04: add   x17, x17, _dyld_private@pageoff
82fe6060f1SDimitry Andric     0xa9bf47f0, // 08: stp   x16/x17, [sp, #-16]!
83fe6060f1SDimitry Andric     0x90000010, // 0c: adrp  x16, dyld_stub_binder@page
84fe6060f1SDimitry Andric     0xf9400210, // 10: ldr   x16, [x16, dyld_stub_binder@pageoff]
85fe6060f1SDimitry Andric     0xd61f0200, // 14: br    x16
86fe6060f1SDimitry Andric };
87fe6060f1SDimitry Andric 
88fe6060f1SDimitry Andric void ARM64::writeStubHelperHeader(uint8_t *buf8) const {
89fe6060f1SDimitry Andric   ::writeStubHelperHeader<LP64>(buf8, stubHelperHeaderCode);
90fe6060f1SDimitry Andric }
91fe6060f1SDimitry Andric 
92fe6060f1SDimitry Andric static constexpr uint32_t stubHelperEntryCode[] = {
93fe6060f1SDimitry Andric     0x18000050, // 00: ldr  w16, l0
94fe6060f1SDimitry Andric     0x14000000, // 04: b    stubHelperHeader
95fe6060f1SDimitry Andric     0x00000000, // 08: l0: .long 0
96fe6060f1SDimitry Andric };
97fe6060f1SDimitry Andric 
9881ad6265SDimitry Andric void ARM64::writeStubHelperEntry(uint8_t *buf8, const Symbol &sym,
99fe6060f1SDimitry Andric                                  uint64_t entryVA) const {
100fe6060f1SDimitry Andric   ::writeStubHelperEntry(buf8, stubHelperEntryCode, sym, entryVA);
101fe6060f1SDimitry Andric }
102fe6060f1SDimitry Andric 
103fe6060f1SDimitry Andric // A thunk is the relaxed variation of stubCode. We don't need the
104fe6060f1SDimitry Andric // extra indirection through a lazy pointer because the target address
105fe6060f1SDimitry Andric // is known at link time.
106fe6060f1SDimitry Andric static constexpr uint32_t thunkCode[] = {
107fe6060f1SDimitry Andric     0x90000010, // 00: adrp  x16, <thunk.ptr>@page
108fe6060f1SDimitry Andric     0x91000210, // 04: add   x16, [x16,<thunk.ptr>@pageoff]
109fe6060f1SDimitry Andric     0xd61f0200, // 08: br    x16
110fe6060f1SDimitry Andric };
111fe6060f1SDimitry Andric 
112fe6060f1SDimitry Andric void ARM64::populateThunk(InputSection *thunk, Symbol *funcSym) {
113fe6060f1SDimitry Andric   thunk->align = 4;
114fe6060f1SDimitry Andric   thunk->data = {reinterpret_cast<const uint8_t *>(thunkCode),
115fe6060f1SDimitry Andric                  sizeof(thunkCode)};
116fe6060f1SDimitry Andric   thunk->relocs.push_back({/*type=*/ARM64_RELOC_PAGEOFF12,
117fe6060f1SDimitry Andric                            /*pcrel=*/false, /*length=*/2,
118fe6060f1SDimitry Andric                            /*offset=*/4, /*addend=*/0,
119fe6060f1SDimitry Andric                            /*referent=*/funcSym});
120fe6060f1SDimitry Andric   thunk->relocs.push_back({/*type=*/ARM64_RELOC_PAGE21,
121fe6060f1SDimitry Andric                            /*pcrel=*/true, /*length=*/2,
122fe6060f1SDimitry Andric                            /*offset=*/0, /*addend=*/0,
123fe6060f1SDimitry Andric                            /*referent=*/funcSym});
124fe6060f1SDimitry Andric }
125fe6060f1SDimitry Andric 
126fe6060f1SDimitry Andric ARM64::ARM64() : ARM64Common(LP64()) {
127fe6060f1SDimitry Andric   cpuType = CPU_TYPE_ARM64;
128fe6060f1SDimitry Andric   cpuSubtype = CPU_SUBTYPE_ARM64_ALL;
129fe6060f1SDimitry Andric 
130fe6060f1SDimitry Andric   stubSize = sizeof(stubCode);
131fe6060f1SDimitry Andric   thunkSize = sizeof(thunkCode);
132349cc55cSDimitry Andric 
133349cc55cSDimitry Andric   // Branch immediate is two's complement 26 bits, which is implicitly
134349cc55cSDimitry Andric   // multiplied by 4 (since all functions are 4-aligned: The branch range
135349cc55cSDimitry Andric   // is -4*(2**(26-1))..4*(2**(26-1) - 1).
136349cc55cSDimitry Andric   backwardBranchRange = 128 * 1024 * 1024;
137349cc55cSDimitry Andric   forwardBranchRange = backwardBranchRange - 4;
138349cc55cSDimitry Andric 
13981ad6265SDimitry Andric   modeDwarfEncoding = UNWIND_ARM64_MODE_DWARF;
14081ad6265SDimitry Andric   subtractorRelocType = ARM64_RELOC_SUBTRACTOR;
14181ad6265SDimitry Andric   unsignedRelocType = ARM64_RELOC_UNSIGNED;
14281ad6265SDimitry Andric 
143fe6060f1SDimitry Andric   stubHelperHeaderSize = sizeof(stubHelperHeaderCode);
144fe6060f1SDimitry Andric   stubHelperEntrySize = sizeof(stubHelperEntryCode);
145*fcaf7f86SDimitry Andric 
146*fcaf7f86SDimitry Andric   relocAttrs = {relocAttrsArray.data(), relocAttrsArray.size()};
147fe6060f1SDimitry Andric }
148fe6060f1SDimitry Andric 
14981ad6265SDimitry Andric namespace {
15081ad6265SDimitry Andric struct Adrp {
15181ad6265SDimitry Andric   uint32_t destRegister;
15281ad6265SDimitry Andric };
15381ad6265SDimitry Andric 
15481ad6265SDimitry Andric struct Add {
15581ad6265SDimitry Andric   uint8_t destRegister;
15681ad6265SDimitry Andric   uint8_t srcRegister;
15781ad6265SDimitry Andric   uint32_t addend;
15881ad6265SDimitry Andric };
15981ad6265SDimitry Andric 
16081ad6265SDimitry Andric enum ExtendType { ZeroExtend = 1, Sign64 = 2, Sign32 = 3 };
16181ad6265SDimitry Andric 
16281ad6265SDimitry Andric struct Ldr {
16381ad6265SDimitry Andric   uint8_t destRegister;
16481ad6265SDimitry Andric   uint8_t baseRegister;
165753f127fSDimitry Andric   uint8_t p2Size;
16681ad6265SDimitry Andric   bool isFloat;
16781ad6265SDimitry Andric   ExtendType extendType;
168753f127fSDimitry Andric   int64_t offset;
16981ad6265SDimitry Andric };
17081ad6265SDimitry Andric 
17181ad6265SDimitry Andric struct PerformedReloc {
17281ad6265SDimitry Andric   const Reloc &rel;
17381ad6265SDimitry Andric   uint64_t referentVA;
17481ad6265SDimitry Andric };
17581ad6265SDimitry Andric 
17681ad6265SDimitry Andric class OptimizationHintContext {
17781ad6265SDimitry Andric public:
17881ad6265SDimitry Andric   OptimizationHintContext(uint8_t *buf, const ConcatInputSection *isec,
17981ad6265SDimitry Andric                           ArrayRef<uint64_t> relocTargets)
18081ad6265SDimitry Andric       : buf(buf), isec(isec), relocTargets(relocTargets),
18181ad6265SDimitry Andric         relocIt(isec->relocs.rbegin()) {}
18281ad6265SDimitry Andric 
18381ad6265SDimitry Andric   void applyAdrpAdd(const OptimizationHint &);
18481ad6265SDimitry Andric   void applyAdrpAdrp(const OptimizationHint &);
18581ad6265SDimitry Andric   void applyAdrpLdr(const OptimizationHint &);
186753f127fSDimitry Andric   void applyAdrpLdrGot(const OptimizationHint &);
187753f127fSDimitry Andric   void applyAdrpLdrGotLdr(const OptimizationHint &);
18881ad6265SDimitry Andric 
18981ad6265SDimitry Andric private:
19081ad6265SDimitry Andric   uint8_t *buf;
19181ad6265SDimitry Andric   const ConcatInputSection *isec;
19281ad6265SDimitry Andric   ArrayRef<uint64_t> relocTargets;
19381ad6265SDimitry Andric   std::vector<Reloc>::const_reverse_iterator relocIt;
19481ad6265SDimitry Andric 
19581ad6265SDimitry Andric   uint64_t getRelocTarget(const Reloc &);
19681ad6265SDimitry Andric 
19781ad6265SDimitry Andric   Optional<PerformedReloc> findPrimaryReloc(uint64_t offset);
19881ad6265SDimitry Andric   Optional<PerformedReloc> findReloc(uint64_t offset);
19981ad6265SDimitry Andric };
20081ad6265SDimitry Andric } // namespace
20181ad6265SDimitry Andric 
20281ad6265SDimitry Andric static bool parseAdrp(uint32_t insn, Adrp &adrp) {
20381ad6265SDimitry Andric   if ((insn & 0x9f000000) != 0x90000000)
20481ad6265SDimitry Andric     return false;
20581ad6265SDimitry Andric   adrp.destRegister = insn & 0x1f;
20681ad6265SDimitry Andric   return true;
20781ad6265SDimitry Andric }
20881ad6265SDimitry Andric 
20981ad6265SDimitry Andric static bool parseAdd(uint32_t insn, Add &add) {
21081ad6265SDimitry Andric   if ((insn & 0xffc00000) != 0x91000000)
21181ad6265SDimitry Andric     return false;
21281ad6265SDimitry Andric   add.destRegister = insn & 0x1f;
21381ad6265SDimitry Andric   add.srcRegister = (insn >> 5) & 0x1f;
21481ad6265SDimitry Andric   add.addend = (insn >> 10) & 0xfff;
21581ad6265SDimitry Andric   return true;
21681ad6265SDimitry Andric }
21781ad6265SDimitry Andric 
21881ad6265SDimitry Andric static bool parseLdr(uint32_t insn, Ldr &ldr) {
21981ad6265SDimitry Andric   ldr.destRegister = insn & 0x1f;
22081ad6265SDimitry Andric   ldr.baseRegister = (insn >> 5) & 0x1f;
22181ad6265SDimitry Andric   uint8_t size = insn >> 30;
22281ad6265SDimitry Andric   uint8_t opc = (insn >> 22) & 3;
22381ad6265SDimitry Andric 
22481ad6265SDimitry Andric   if ((insn & 0x3fc00000) == 0x39400000) {
22581ad6265SDimitry Andric     // LDR (immediate), LDRB (immediate), LDRH (immediate)
226753f127fSDimitry Andric     ldr.p2Size = size;
22781ad6265SDimitry Andric     ldr.extendType = ZeroExtend;
22881ad6265SDimitry Andric     ldr.isFloat = false;
22981ad6265SDimitry Andric   } else if ((insn & 0x3f800000) == 0x39800000) {
23081ad6265SDimitry Andric     // LDRSB (immediate), LDRSH (immediate), LDRSW (immediate)
231753f127fSDimitry Andric     ldr.p2Size = size;
23281ad6265SDimitry Andric     ldr.extendType = static_cast<ExtendType>(opc);
23381ad6265SDimitry Andric     ldr.isFloat = false;
23481ad6265SDimitry Andric   } else if ((insn & 0x3f400000) == 0x3d400000) {
23581ad6265SDimitry Andric     // LDR (immediate, SIMD&FP)
23681ad6265SDimitry Andric     ldr.extendType = ZeroExtend;
23781ad6265SDimitry Andric     ldr.isFloat = true;
238753f127fSDimitry Andric     if (opc == 1)
239753f127fSDimitry Andric       ldr.p2Size = size;
24081ad6265SDimitry Andric     else if (size == 0 && opc == 3)
241753f127fSDimitry Andric       ldr.p2Size = 4;
24281ad6265SDimitry Andric     else
24381ad6265SDimitry Andric       return false;
24481ad6265SDimitry Andric   } else {
24581ad6265SDimitry Andric     return false;
24681ad6265SDimitry Andric   }
247753f127fSDimitry Andric   ldr.offset = ((insn >> 10) & 0xfff) << ldr.p2Size;
24881ad6265SDimitry Andric   return true;
24981ad6265SDimitry Andric }
25081ad6265SDimitry Andric 
251753f127fSDimitry Andric static bool isValidAdrOffset(int32_t delta) { return isInt<21>(delta); }
252753f127fSDimitry Andric 
25381ad6265SDimitry Andric static void writeAdr(void *loc, uint32_t dest, int32_t delta) {
254753f127fSDimitry Andric   assert(isValidAdrOffset(delta));
25581ad6265SDimitry Andric   uint32_t opcode = 0x10000000;
25681ad6265SDimitry Andric   uint32_t immHi = (delta & 0x001ffffc) << 3;
25781ad6265SDimitry Andric   uint32_t immLo = (delta & 0x00000003) << 29;
25881ad6265SDimitry Andric   write32le(loc, opcode | immHi | immLo | dest);
25981ad6265SDimitry Andric }
26081ad6265SDimitry Andric 
26181ad6265SDimitry Andric static void writeNop(void *loc) { write32le(loc, 0xd503201f); }
26281ad6265SDimitry Andric 
263753f127fSDimitry Andric static bool isLiteralLdrEligible(const Ldr &ldr) {
264753f127fSDimitry Andric   return ldr.p2Size > 1 && isShiftedInt<19, 2>(ldr.offset);
265753f127fSDimitry Andric }
266753f127fSDimitry Andric 
267753f127fSDimitry Andric static void writeLiteralLdr(void *loc, const Ldr &ldr) {
268753f127fSDimitry Andric   assert(isLiteralLdrEligible(ldr));
269753f127fSDimitry Andric   uint32_t imm19 = (ldr.offset / 4 & maskTrailingOnes<uint32_t>(19)) << 5;
270753f127fSDimitry Andric   uint32_t opcode;
271753f127fSDimitry Andric   switch (ldr.p2Size) {
272753f127fSDimitry Andric   case 2:
273753f127fSDimitry Andric     if (ldr.isFloat)
27481ad6265SDimitry Andric       opcode = 0x1c000000;
27581ad6265SDimitry Andric     else
276753f127fSDimitry Andric       opcode = ldr.extendType == Sign64 ? 0x98000000 : 0x18000000;
27781ad6265SDimitry Andric     break;
278753f127fSDimitry Andric   case 3:
279753f127fSDimitry Andric     opcode = ldr.isFloat ? 0x5c000000 : 0x58000000;
28081ad6265SDimitry Andric     break;
281753f127fSDimitry Andric   case 4:
28281ad6265SDimitry Andric     opcode = 0x9c000000;
28381ad6265SDimitry Andric     break;
28481ad6265SDimitry Andric   default:
285753f127fSDimitry Andric     llvm_unreachable("Invalid literal ldr size");
28681ad6265SDimitry Andric   }
287753f127fSDimitry Andric   write32le(loc, opcode | imm19 | ldr.destRegister);
288753f127fSDimitry Andric }
289753f127fSDimitry Andric 
290753f127fSDimitry Andric static bool isImmediateLdrEligible(const Ldr &ldr) {
291753f127fSDimitry Andric   // Note: We deviate from ld64's behavior, which converts to immediate loads
292753f127fSDimitry Andric   // only if ldr.offset < 4096, even though the offset is divided by the load's
293753f127fSDimitry Andric   // size in the 12-bit immediate operand. Only the unsigned offset variant is
294753f127fSDimitry Andric   // supported.
295753f127fSDimitry Andric 
296753f127fSDimitry Andric   uint32_t size = 1 << ldr.p2Size;
297753f127fSDimitry Andric   return ldr.offset >= 0 && (ldr.offset % size) == 0 &&
298753f127fSDimitry Andric          isUInt<12>(ldr.offset >> ldr.p2Size);
299753f127fSDimitry Andric }
300753f127fSDimitry Andric 
301753f127fSDimitry Andric static void writeImmediateLdr(void *loc, const Ldr &ldr) {
302753f127fSDimitry Andric   assert(isImmediateLdrEligible(ldr));
303753f127fSDimitry Andric   uint32_t opcode = 0x39000000;
304753f127fSDimitry Andric   if (ldr.isFloat) {
305753f127fSDimitry Andric     opcode |= 0x04000000;
306753f127fSDimitry Andric     assert(ldr.extendType == ZeroExtend);
307753f127fSDimitry Andric   }
308753f127fSDimitry Andric   opcode |= ldr.destRegister;
309753f127fSDimitry Andric   opcode |= ldr.baseRegister << 5;
310753f127fSDimitry Andric   uint8_t size, opc;
311753f127fSDimitry Andric   if (ldr.p2Size == 4) {
312753f127fSDimitry Andric     size = 0;
313753f127fSDimitry Andric     opc = 3;
314753f127fSDimitry Andric   } else {
315753f127fSDimitry Andric     opc = ldr.extendType;
316753f127fSDimitry Andric     size = ldr.p2Size;
317753f127fSDimitry Andric   }
318753f127fSDimitry Andric   uint32_t immBits = ldr.offset >> ldr.p2Size;
319753f127fSDimitry Andric   write32le(loc, opcode | (immBits << 10) | (opc << 22) | (size << 30));
32081ad6265SDimitry Andric }
32181ad6265SDimitry Andric 
32281ad6265SDimitry Andric uint64_t OptimizationHintContext::getRelocTarget(const Reloc &reloc) {
32381ad6265SDimitry Andric   size_t relocIdx = &reloc - isec->relocs.data();
32481ad6265SDimitry Andric   return relocTargets[relocIdx];
32581ad6265SDimitry Andric }
32681ad6265SDimitry Andric 
32781ad6265SDimitry Andric // Optimization hints are sorted in a monotonically increasing order by their
32881ad6265SDimitry Andric // first address as are relocations (albeit in decreasing order), so if we keep
32981ad6265SDimitry Andric // a pointer around to the last found relocation, we don't have to do a full
33081ad6265SDimitry Andric // binary search every time.
33181ad6265SDimitry Andric Optional<PerformedReloc>
33281ad6265SDimitry Andric OptimizationHintContext::findPrimaryReloc(uint64_t offset) {
33381ad6265SDimitry Andric   const auto end = isec->relocs.rend();
33481ad6265SDimitry Andric   while (relocIt != end && relocIt->offset < offset)
33581ad6265SDimitry Andric     ++relocIt;
33681ad6265SDimitry Andric   if (relocIt == end || relocIt->offset != offset)
33781ad6265SDimitry Andric     return None;
33881ad6265SDimitry Andric   return PerformedReloc{*relocIt, getRelocTarget(*relocIt)};
33981ad6265SDimitry Andric }
34081ad6265SDimitry Andric 
34181ad6265SDimitry Andric // The second and third addresses of optimization hints have no such
34281ad6265SDimitry Andric // monotonicity as the first, so we search the entire range of relocations.
34381ad6265SDimitry Andric Optional<PerformedReloc> OptimizationHintContext::findReloc(uint64_t offset) {
34481ad6265SDimitry Andric   // Optimization hints often apply to successive relocations, so we check for
34581ad6265SDimitry Andric   // that first before doing a full binary search.
34681ad6265SDimitry Andric   auto end = isec->relocs.rend();
34781ad6265SDimitry Andric   if (relocIt < end - 1 && (relocIt + 1)->offset == offset)
34881ad6265SDimitry Andric     return PerformedReloc{*(relocIt + 1), getRelocTarget(*(relocIt + 1))};
34981ad6265SDimitry Andric 
35081ad6265SDimitry Andric   auto reloc = lower_bound(isec->relocs, offset,
35181ad6265SDimitry Andric                            [](const Reloc &reloc, uint64_t offset) {
35281ad6265SDimitry Andric                              return offset < reloc.offset;
35381ad6265SDimitry Andric                            });
35481ad6265SDimitry Andric 
35581ad6265SDimitry Andric   if (reloc == isec->relocs.end() || reloc->offset != offset)
35681ad6265SDimitry Andric     return None;
35781ad6265SDimitry Andric   return PerformedReloc{*reloc, getRelocTarget(*reloc)};
35881ad6265SDimitry Andric }
35981ad6265SDimitry Andric 
36081ad6265SDimitry Andric // Transforms a pair of adrp+add instructions into an adr instruction if the
36181ad6265SDimitry Andric // target is within the +/- 1 MiB range allowed by the adr's 21 bit signed
36281ad6265SDimitry Andric // immediate offset.
36381ad6265SDimitry Andric //
36481ad6265SDimitry Andric //   adrp xN, _foo@PAGE
36581ad6265SDimitry Andric //   add  xM, xN, _foo@PAGEOFF
36681ad6265SDimitry Andric // ->
36781ad6265SDimitry Andric //   adr  xM, _foo
36881ad6265SDimitry Andric //   nop
36981ad6265SDimitry Andric void OptimizationHintContext::applyAdrpAdd(const OptimizationHint &hint) {
37081ad6265SDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
37181ad6265SDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
37281ad6265SDimitry Andric   Adrp adrp;
37381ad6265SDimitry Andric   if (!parseAdrp(ins1, adrp))
37481ad6265SDimitry Andric     return;
37581ad6265SDimitry Andric   Add add;
37681ad6265SDimitry Andric   if (!parseAdd(ins2, add))
37781ad6265SDimitry Andric     return;
37881ad6265SDimitry Andric   if (adrp.destRegister != add.srcRegister)
37981ad6265SDimitry Andric     return;
38081ad6265SDimitry Andric 
38181ad6265SDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
38281ad6265SDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
38381ad6265SDimitry Andric   if (!rel1 || !rel2)
38481ad6265SDimitry Andric     return;
38581ad6265SDimitry Andric   if (rel1->referentVA != rel2->referentVA)
38681ad6265SDimitry Andric     return;
38781ad6265SDimitry Andric   int64_t delta = rel1->referentVA - rel1->rel.offset - isec->getVA();
388753f127fSDimitry Andric   if (!isValidAdrOffset(delta))
38981ad6265SDimitry Andric     return;
39081ad6265SDimitry Andric 
39181ad6265SDimitry Andric   writeAdr(buf + hint.offset0, add.destRegister, delta);
39281ad6265SDimitry Andric   writeNop(buf + hint.offset0 + hint.delta[0]);
39381ad6265SDimitry Andric }
39481ad6265SDimitry Andric 
39581ad6265SDimitry Andric // Transforms two adrp instructions into a single adrp if their referent
39681ad6265SDimitry Andric // addresses are located on the same 4096 byte page.
39781ad6265SDimitry Andric //
39881ad6265SDimitry Andric //   adrp xN, _foo@PAGE
39981ad6265SDimitry Andric //   adrp xN, _bar@PAGE
40081ad6265SDimitry Andric // ->
40181ad6265SDimitry Andric //   adrp xN, _foo@PAGE
40281ad6265SDimitry Andric //   nop
40381ad6265SDimitry Andric void OptimizationHintContext::applyAdrpAdrp(const OptimizationHint &hint) {
40481ad6265SDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
40581ad6265SDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
40681ad6265SDimitry Andric   Adrp adrp1, adrp2;
40781ad6265SDimitry Andric   if (!parseAdrp(ins1, adrp1) || !parseAdrp(ins2, adrp2))
40881ad6265SDimitry Andric     return;
40981ad6265SDimitry Andric   if (adrp1.destRegister != adrp2.destRegister)
41081ad6265SDimitry Andric     return;
41181ad6265SDimitry Andric 
41281ad6265SDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
41381ad6265SDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
41481ad6265SDimitry Andric   if (!rel1 || !rel2)
41581ad6265SDimitry Andric     return;
41681ad6265SDimitry Andric   if ((rel1->referentVA & ~0xfffULL) != (rel2->referentVA & ~0xfffULL))
41781ad6265SDimitry Andric     return;
41881ad6265SDimitry Andric 
41981ad6265SDimitry Andric   writeNop(buf + hint.offset0 + hint.delta[0]);
42081ad6265SDimitry Andric }
42181ad6265SDimitry Andric 
42281ad6265SDimitry Andric // Transforms a pair of adrp+ldr (immediate) instructions into an ldr (literal)
42381ad6265SDimitry Andric // load from a PC-relative address if it is 4-byte aligned and within +/- 1 MiB,
42481ad6265SDimitry Andric // as ldr can encode a signed 19-bit offset that gets multiplied by 4.
42581ad6265SDimitry Andric //
42681ad6265SDimitry Andric //   adrp xN, _foo@PAGE
42781ad6265SDimitry Andric //   ldr  xM, [xN, _foo@PAGEOFF]
42881ad6265SDimitry Andric // ->
42981ad6265SDimitry Andric //   nop
43081ad6265SDimitry Andric //   ldr  xM, _foo
43181ad6265SDimitry Andric void OptimizationHintContext::applyAdrpLdr(const OptimizationHint &hint) {
43281ad6265SDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
43381ad6265SDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
43481ad6265SDimitry Andric   Adrp adrp;
43581ad6265SDimitry Andric   if (!parseAdrp(ins1, adrp))
43681ad6265SDimitry Andric     return;
43781ad6265SDimitry Andric   Ldr ldr;
43881ad6265SDimitry Andric   if (!parseLdr(ins2, ldr))
43981ad6265SDimitry Andric     return;
44081ad6265SDimitry Andric   if (adrp.destRegister != ldr.baseRegister)
44181ad6265SDimitry Andric     return;
44281ad6265SDimitry Andric 
44381ad6265SDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
44481ad6265SDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
44581ad6265SDimitry Andric   if (!rel1 || !rel2)
44681ad6265SDimitry Andric     return;
44781ad6265SDimitry Andric   if (ldr.offset != (rel1->referentVA & 0xfff))
44881ad6265SDimitry Andric     return;
449753f127fSDimitry Andric   ldr.offset = rel1->referentVA - rel2->rel.offset - isec->getVA();
450753f127fSDimitry Andric   if (!isLiteralLdrEligible(ldr))
45181ad6265SDimitry Andric     return;
45281ad6265SDimitry Andric 
45381ad6265SDimitry Andric   writeNop(buf + hint.offset0);
454753f127fSDimitry Andric   writeLiteralLdr(buf + hint.offset0 + hint.delta[0], ldr);
455753f127fSDimitry Andric }
456753f127fSDimitry Andric 
457753f127fSDimitry Andric // GOT loads are emitted by the compiler as a pair of adrp and ldr instructions,
458753f127fSDimitry Andric // but they may be changed to adrp+add by relaxGotLoad(). This hint performs
459753f127fSDimitry Andric // the AdrpLdr or AdrpAdd transformation depending on whether it was relaxed.
460753f127fSDimitry Andric void OptimizationHintContext::applyAdrpLdrGot(const OptimizationHint &hint) {
461753f127fSDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
462753f127fSDimitry Andric   Add add;
463753f127fSDimitry Andric   Ldr ldr;
464753f127fSDimitry Andric   if (parseAdd(ins2, add))
465753f127fSDimitry Andric     applyAdrpAdd(hint);
466753f127fSDimitry Andric   else if (parseLdr(ins2, ldr))
467753f127fSDimitry Andric     applyAdrpLdr(hint);
468753f127fSDimitry Andric }
469753f127fSDimitry Andric 
470753f127fSDimitry Andric // Relaxes a GOT-indirect load.
471753f127fSDimitry Andric // If the referenced symbol is external and its GOT entry is within +/- 1 MiB,
472753f127fSDimitry Andric // the GOT entry can be loaded with a single literal ldr instruction.
473753f127fSDimitry Andric // If the referenced symbol is local, its address may be loaded directly if it's
474753f127fSDimitry Andric // close enough, or with an adr(p) + ldr pair if it's not.
475753f127fSDimitry Andric void OptimizationHintContext::applyAdrpLdrGotLdr(const OptimizationHint &hint) {
476753f127fSDimitry Andric   uint32_t ins1 = read32le(buf + hint.offset0);
477753f127fSDimitry Andric   Adrp adrp;
478753f127fSDimitry Andric   if (!parseAdrp(ins1, adrp))
479753f127fSDimitry Andric     return;
480753f127fSDimitry Andric   uint32_t ins3 = read32le(buf + hint.offset0 + hint.delta[1]);
481753f127fSDimitry Andric   Ldr ldr3;
482753f127fSDimitry Andric   if (!parseLdr(ins3, ldr3))
483753f127fSDimitry Andric     return;
484753f127fSDimitry Andric   uint32_t ins2 = read32le(buf + hint.offset0 + hint.delta[0]);
485753f127fSDimitry Andric   Ldr ldr2;
486753f127fSDimitry Andric   Add add2;
487753f127fSDimitry Andric 
488753f127fSDimitry Andric   Optional<PerformedReloc> rel1 = findPrimaryReloc(hint.offset0);
489753f127fSDimitry Andric   Optional<PerformedReloc> rel2 = findReloc(hint.offset0 + hint.delta[0]);
490753f127fSDimitry Andric   if (!rel1 || !rel2)
491753f127fSDimitry Andric     return;
492753f127fSDimitry Andric 
493753f127fSDimitry Andric   if (parseAdd(ins2, add2)) {
494753f127fSDimitry Andric     // adrp x0, _foo@PAGE
495753f127fSDimitry Andric     // add  x1, x0, _foo@PAGEOFF
496753f127fSDimitry Andric     // ldr  x2, [x1, #off]
497753f127fSDimitry Andric 
498753f127fSDimitry Andric     if (adrp.destRegister != add2.srcRegister)
499753f127fSDimitry Andric       return;
500753f127fSDimitry Andric     if (add2.destRegister != ldr3.baseRegister)
501753f127fSDimitry Andric       return;
502753f127fSDimitry Andric 
503753f127fSDimitry Andric     // Load from the target address directly.
504753f127fSDimitry Andric     //   nop
505753f127fSDimitry Andric     //   nop
506753f127fSDimitry Andric     //   ldr x2, [_foo + #off]
507753f127fSDimitry Andric     uint64_t rel3VA = hint.offset0 + hint.delta[1] + isec->getVA();
508753f127fSDimitry Andric     Ldr literalLdr = ldr3;
509753f127fSDimitry Andric     literalLdr.offset += rel1->referentVA - rel3VA;
510753f127fSDimitry Andric     if (isLiteralLdrEligible(literalLdr)) {
511753f127fSDimitry Andric       writeNop(buf + hint.offset0);
512753f127fSDimitry Andric       writeNop(buf + hint.offset0 + hint.delta[0]);
513753f127fSDimitry Andric       writeLiteralLdr(buf + hint.offset0 + hint.delta[1], literalLdr);
514753f127fSDimitry Andric       return;
515753f127fSDimitry Andric     }
516753f127fSDimitry Andric 
517753f127fSDimitry Andric     // Load the target address into a register and load from there indirectly.
518753f127fSDimitry Andric     //   adr x1, _foo
519753f127fSDimitry Andric     //   nop
520753f127fSDimitry Andric     //   ldr x2, [x1, #off]
521753f127fSDimitry Andric     int64_t adrOffset = rel1->referentVA - rel1->rel.offset - isec->getVA();
522753f127fSDimitry Andric     if (isValidAdrOffset(adrOffset)) {
523753f127fSDimitry Andric       writeAdr(buf + hint.offset0, ldr3.baseRegister, adrOffset);
524753f127fSDimitry Andric       writeNop(buf + hint.offset0 + hint.delta[0]);
525753f127fSDimitry Andric       return;
526753f127fSDimitry Andric     }
527753f127fSDimitry Andric 
528753f127fSDimitry Andric     // Move the target's page offset into the ldr's immediate offset.
529753f127fSDimitry Andric     //   adrp x0, _foo@PAGE
530753f127fSDimitry Andric     //   nop
531753f127fSDimitry Andric     //   ldr x2, [x0, _foo@PAGEOFF + #off]
532753f127fSDimitry Andric     Ldr immediateLdr = ldr3;
533753f127fSDimitry Andric     immediateLdr.baseRegister = adrp.destRegister;
534753f127fSDimitry Andric     immediateLdr.offset += add2.addend;
535753f127fSDimitry Andric     if (isImmediateLdrEligible(immediateLdr)) {
536753f127fSDimitry Andric       writeNop(buf + hint.offset0 + hint.delta[0]);
537753f127fSDimitry Andric       writeImmediateLdr(buf + hint.offset0 + hint.delta[1], immediateLdr);
538753f127fSDimitry Andric       return;
539753f127fSDimitry Andric     }
540753f127fSDimitry Andric   } else if (parseLdr(ins2, ldr2)) {
541753f127fSDimitry Andric     // adrp x1, _foo@GOTPAGE
542753f127fSDimitry Andric     // ldr  x2, [x1, _foo@GOTPAGEOFF]
543753f127fSDimitry Andric     // ldr  x3, [x2, #off]
544753f127fSDimitry Andric     if (ldr2.baseRegister != adrp.destRegister)
545753f127fSDimitry Andric       return;
546753f127fSDimitry Andric     if (ldr3.baseRegister != ldr2.destRegister)
547753f127fSDimitry Andric       return;
548753f127fSDimitry Andric     // Loads from the GOT must be pointer sized.
549753f127fSDimitry Andric     if (ldr2.p2Size != 3 || ldr2.isFloat)
550753f127fSDimitry Andric       return;
551753f127fSDimitry Andric 
552753f127fSDimitry Andric     // Load the GOT entry's address directly.
553753f127fSDimitry Andric     //   nop
554753f127fSDimitry Andric     //   ldr x2, _foo@GOTPAGE + _foo@GOTPAGEOFF
555753f127fSDimitry Andric     //   ldr x3, [x2, #off]
556753f127fSDimitry Andric     Ldr literalLdr = ldr2;
557753f127fSDimitry Andric     literalLdr.offset = rel1->referentVA - rel2->rel.offset - isec->getVA();
558753f127fSDimitry Andric     if (isLiteralLdrEligible(literalLdr)) {
559753f127fSDimitry Andric       writeNop(buf + hint.offset0);
560753f127fSDimitry Andric       writeLiteralLdr(buf + hint.offset0 + hint.delta[0], literalLdr);
561753f127fSDimitry Andric     }
562753f127fSDimitry Andric   }
56381ad6265SDimitry Andric }
56481ad6265SDimitry Andric 
56581ad6265SDimitry Andric void ARM64::applyOptimizationHints(uint8_t *buf, const ConcatInputSection *isec,
56681ad6265SDimitry Andric                                    ArrayRef<uint64_t> relocTargets) const {
56781ad6265SDimitry Andric   assert(isec);
56881ad6265SDimitry Andric   assert(relocTargets.size() == isec->relocs.size());
56981ad6265SDimitry Andric 
57081ad6265SDimitry Andric   // Note: Some of these optimizations might not be valid when shared regions
57181ad6265SDimitry Andric   // are in use. Will need to revisit this if splitSegInfo is added.
57281ad6265SDimitry Andric 
57381ad6265SDimitry Andric   OptimizationHintContext ctx1(buf, isec, relocTargets);
57481ad6265SDimitry Andric   for (const OptimizationHint &hint : isec->optimizationHints) {
57581ad6265SDimitry Andric     switch (hint.type) {
57681ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADRP:
57781ad6265SDimitry Andric       // This is done in another pass because the other optimization hints
57881ad6265SDimitry Andric       // might cause its targets to be turned into NOPs.
57981ad6265SDimitry Andric       break;
58081ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR:
58181ad6265SDimitry Andric       ctx1.applyAdrpLdr(hint);
58281ad6265SDimitry Andric       break;
58381ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADD_LDR:
584753f127fSDimitry Andric       // TODO: Implement this
585753f127fSDimitry Andric       break;
58681ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR_GOT_LDR:
587753f127fSDimitry Andric       ctx1.applyAdrpLdrGotLdr(hint);
588753f127fSDimitry Andric       break;
58981ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADD_STR:
59081ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR_GOT_STR:
59181ad6265SDimitry Andric       // TODO: Implement these
59281ad6265SDimitry Andric       break;
59381ad6265SDimitry Andric     case LOH_ARM64_ADRP_ADD:
59481ad6265SDimitry Andric       ctx1.applyAdrpAdd(hint);
59581ad6265SDimitry Andric       break;
59681ad6265SDimitry Andric     case LOH_ARM64_ADRP_LDR_GOT:
597753f127fSDimitry Andric       ctx1.applyAdrpLdrGot(hint);
59881ad6265SDimitry Andric       break;
59981ad6265SDimitry Andric     }
60081ad6265SDimitry Andric   }
60181ad6265SDimitry Andric 
60281ad6265SDimitry Andric   OptimizationHintContext ctx2(buf, isec, relocTargets);
60381ad6265SDimitry Andric   for (const OptimizationHint &hint : isec->optimizationHints)
60481ad6265SDimitry Andric     if (hint.type == LOH_ARM64_ADRP_ADRP)
60581ad6265SDimitry Andric       ctx2.applyAdrpAdrp(hint);
60681ad6265SDimitry Andric }
60781ad6265SDimitry Andric 
608fe6060f1SDimitry Andric TargetInfo *macho::createARM64TargetInfo() {
609fe6060f1SDimitry Andric   static ARM64 t;
610fe6060f1SDimitry Andric   return &t;
611fe6060f1SDimitry Andric }
612