xref: /llvm-project/llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp (revision 8c37e3e64bb1432f771ec4d191837e6b3be5bf0c)
1 //===------- ELF_riscv.cpp -JIT linker implementation for ELF/riscv -------===//
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 // ELF/riscv jit-link implementation.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ExecutionEngine/JITLink/ELF_riscv.h"
14 #include "EHFrameSupportImpl.h"
15 #include "ELFLinkGraphBuilder.h"
16 #include "JITLinkGeneric.h"
17 #include "PerGraphGOTAndPLTStubsBuilder.h"
18 #include "llvm/BinaryFormat/ELF.h"
19 #include "llvm/ExecutionEngine/JITLink/DWARFRecordSectionSplitter.h"
20 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
21 #include "llvm/ExecutionEngine/JITLink/riscv.h"
22 #include "llvm/Object/ELF.h"
23 #include "llvm/Object/ELFObjectFile.h"
24 #include "llvm/Support/Endian.h"
25 
26 #define DEBUG_TYPE "jitlink"
27 using namespace llvm;
28 using namespace llvm::jitlink;
29 using namespace llvm::jitlink::riscv;
30 
31 namespace {
32 
33 class PerGraphGOTAndPLTStubsBuilder_ELF_riscv
34     : public PerGraphGOTAndPLTStubsBuilder<
35           PerGraphGOTAndPLTStubsBuilder_ELF_riscv> {
36 public:
37   static constexpr size_t StubEntrySize = 16;
38   static const uint8_t NullGOTEntryContent[8];
39   static const uint8_t RV64StubContent[StubEntrySize];
40   static const uint8_t RV32StubContent[StubEntrySize];
41 
42   using PerGraphGOTAndPLTStubsBuilder<
43       PerGraphGOTAndPLTStubsBuilder_ELF_riscv>::PerGraphGOTAndPLTStubsBuilder;
44 
45   bool isRV64() const { return G.getPointerSize() == 8; }
46 
47   bool isGOTEdgeToFix(Edge &E) const { return E.getKind() == R_RISCV_GOT_HI20; }
48 
49   Symbol &createGOTEntry(Symbol &Target) {
50     Block &GOTBlock =
51         G.createContentBlock(getGOTSection(), getGOTEntryBlockContent(),
52                              orc::ExecutorAddr(), G.getPointerSize(), 0);
53     GOTBlock.addEdge(isRV64() ? R_RISCV_64 : R_RISCV_32, 0, Target, 0);
54     return G.addAnonymousSymbol(GOTBlock, 0, G.getPointerSize(), false, false);
55   }
56 
57   Symbol &createPLTStub(Symbol &Target) {
58     Block &StubContentBlock = G.createContentBlock(
59         getStubsSection(), getStubBlockContent(), orc::ExecutorAddr(), 4, 0);
60     auto &GOTEntrySymbol = getGOTEntry(Target);
61     StubContentBlock.addEdge(R_RISCV_CALL, 0, GOTEntrySymbol, 0);
62     return G.addAnonymousSymbol(StubContentBlock, 0, StubEntrySize, true,
63                                 false);
64   }
65 
66   void fixGOTEdge(Edge &E, Symbol &GOTEntry) {
67     // Replace the relocation pair (R_RISCV_GOT_HI20, R_RISCV_PCREL_LO12)
68     // with (R_RISCV_PCREL_HI20, R_RISCV_PCREL_LO12)
69     // Therefore, here just change the R_RISCV_GOT_HI20 to R_RISCV_PCREL_HI20
70     E.setKind(R_RISCV_PCREL_HI20);
71     E.setTarget(GOTEntry);
72   }
73 
74   void fixPLTEdge(Edge &E, Symbol &PLTStubs) {
75     assert((E.getKind() == R_RISCV_CALL || E.getKind() == R_RISCV_CALL_PLT ||
76             E.getKind() == CallRelaxable) &&
77            "Not a PLT edge?");
78     E.setKind(R_RISCV_CALL);
79     E.setTarget(PLTStubs);
80   }
81 
82   bool isExternalBranchEdge(Edge &E) const {
83     return (E.getKind() == R_RISCV_CALL || E.getKind() == R_RISCV_CALL_PLT ||
84             E.getKind() == CallRelaxable) &&
85            !E.getTarget().isDefined();
86   }
87 
88 private:
89   Section &getGOTSection() const {
90     if (!GOTSection)
91       GOTSection = &G.createSection("$__GOT", orc::MemProt::Read);
92     return *GOTSection;
93   }
94 
95   Section &getStubsSection() const {
96     if (!StubsSection)
97       StubsSection =
98           &G.createSection("$__STUBS", orc::MemProt::Read | orc::MemProt::Exec);
99     return *StubsSection;
100   }
101 
102   ArrayRef<char> getGOTEntryBlockContent() {
103     return {reinterpret_cast<const char *>(NullGOTEntryContent),
104             G.getPointerSize()};
105   }
106 
107   ArrayRef<char> getStubBlockContent() {
108     auto StubContent = isRV64() ? RV64StubContent : RV32StubContent;
109     return {reinterpret_cast<const char *>(StubContent), StubEntrySize};
110   }
111 
112   mutable Section *GOTSection = nullptr;
113   mutable Section *StubsSection = nullptr;
114 };
115 
116 const uint8_t PerGraphGOTAndPLTStubsBuilder_ELF_riscv::NullGOTEntryContent[8] =
117     {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
118 
119 const uint8_t
120     PerGraphGOTAndPLTStubsBuilder_ELF_riscv::RV64StubContent[StubEntrySize] = {
121         0x17, 0x0e, 0x00, 0x00,  // auipc t3, literal
122         0x03, 0x3e, 0x0e, 0x00,  // ld    t3, literal(t3)
123         0x67, 0x00, 0x0e, 0x00,  // jr    t3
124         0x13, 0x00, 0x00, 0x00}; // nop
125 
126 const uint8_t
127     PerGraphGOTAndPLTStubsBuilder_ELF_riscv::RV32StubContent[StubEntrySize] = {
128         0x17, 0x0e, 0x00, 0x00,  // auipc t3, literal
129         0x03, 0x2e, 0x0e, 0x00,  // lw    t3, literal(t3)
130         0x67, 0x00, 0x0e, 0x00,  // jr    t3
131         0x13, 0x00, 0x00, 0x00}; // nop
132 } // namespace
133 namespace llvm {
134 namespace jitlink {
135 
136 static Expected<const Edge &> getRISCVPCRelHi20(const Edge &E) {
137   using namespace riscv;
138   assert((E.getKind() == R_RISCV_PCREL_LO12_I ||
139           E.getKind() == R_RISCV_PCREL_LO12_S) &&
140          "Can only have high relocation for R_RISCV_PCREL_LO12_I or "
141          "R_RISCV_PCREL_LO12_S");
142 
143   const Symbol &Sym = E.getTarget();
144   const Block &B = Sym.getBlock();
145   orc::ExecutorAddrDiff Offset = Sym.getOffset();
146 
147   struct Comp {
148     bool operator()(const Edge &Lhs, orc::ExecutorAddrDiff Offset) {
149       return Lhs.getOffset() < Offset;
150     }
151     bool operator()(orc::ExecutorAddrDiff Offset, const Edge &Rhs) {
152       return Offset < Rhs.getOffset();
153     }
154   };
155 
156   auto Bound =
157       std::equal_range(B.edges().begin(), B.edges().end(), Offset, Comp{});
158 
159   for (auto It = Bound.first; It != Bound.second; ++It) {
160     if (It->getKind() == R_RISCV_PCREL_HI20)
161       return *It;
162   }
163 
164   return make_error<JITLinkError>(
165       "No HI20 PCREL relocation type be found for LO12 PCREL relocation type");
166 }
167 
168 static uint32_t extractBits(uint32_t Num, unsigned Low, unsigned Size) {
169   return (Num & (((1ULL << Size) - 1) << Low)) >> Low;
170 }
171 
172 static inline bool isAlignmentCorrect(uint64_t Value, int N) {
173   return (Value & (N - 1)) ? false : true;
174 }
175 
176 // Requires 0 < N <= 64.
177 static inline bool isInRangeForImm(int64_t Value, int N) {
178   return Value == llvm::SignExtend64(Value, N);
179 }
180 
181 class ELFJITLinker_riscv : public JITLinker<ELFJITLinker_riscv> {
182   friend class JITLinker<ELFJITLinker_riscv>;
183 
184 public:
185   ELFJITLinker_riscv(std::unique_ptr<JITLinkContext> Ctx,
186                      std::unique_ptr<LinkGraph> G, PassConfiguration PassConfig)
187       : JITLinker(std::move(Ctx), std::move(G), std::move(PassConfig)) {}
188 
189 private:
190   Error applyFixup(LinkGraph &G, Block &B, const Edge &E) const {
191     using namespace riscv;
192     using namespace llvm::support;
193 
194     char *BlockWorkingMem = B.getAlreadyMutableContent().data();
195     char *FixupPtr = BlockWorkingMem + E.getOffset();
196     orc::ExecutorAddr FixupAddress = B.getAddress() + E.getOffset();
197     switch (E.getKind()) {
198     case R_RISCV_32: {
199       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
200       *(little32_t *)FixupPtr = static_cast<uint32_t>(Value);
201       break;
202     }
203     case R_RISCV_64: {
204       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
205       *(little64_t *)FixupPtr = static_cast<uint64_t>(Value);
206       break;
207     }
208     case R_RISCV_BRANCH: {
209       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
210       if (LLVM_UNLIKELY(!isInRangeForImm(Value >> 1, 12)))
211         return makeTargetOutOfRangeError(G, B, E);
212       if (LLVM_UNLIKELY(!isAlignmentCorrect(Value, 2)))
213         return makeAlignmentError(FixupAddress, Value, 2, E);
214       uint32_t Imm12 = extractBits(Value, 12, 1) << 31;
215       uint32_t Imm10_5 = extractBits(Value, 5, 6) << 25;
216       uint32_t Imm4_1 = extractBits(Value, 1, 4) << 8;
217       uint32_t Imm11 = extractBits(Value, 11, 1) << 7;
218       uint32_t RawInstr = *(little32_t *)FixupPtr;
219       *(little32_t *)FixupPtr =
220           (RawInstr & 0x1FFF07F) | Imm12 | Imm10_5 | Imm4_1 | Imm11;
221       break;
222     }
223     case R_RISCV_JAL: {
224       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
225       if (LLVM_UNLIKELY(!isInRangeForImm(Value >> 1, 20)))
226         return makeTargetOutOfRangeError(G, B, E);
227       if (LLVM_UNLIKELY(!isAlignmentCorrect(Value, 2)))
228         return makeAlignmentError(FixupAddress, Value, 2, E);
229       uint32_t Imm20 = extractBits(Value, 20, 1) << 31;
230       uint32_t Imm10_1 = extractBits(Value, 1, 10) << 21;
231       uint32_t Imm11 = extractBits(Value, 11, 1) << 20;
232       uint32_t Imm19_12 = extractBits(Value, 12, 8) << 12;
233       uint32_t RawInstr = *(little32_t *)FixupPtr;
234       *(little32_t *)FixupPtr =
235           (RawInstr & 0xFFF) | Imm20 | Imm10_1 | Imm11 | Imm19_12;
236       break;
237     }
238     case CallRelaxable:
239       // Treat as R_RISCV_CALL when the relaxation pass did not run
240     case R_RISCV_CALL_PLT:
241     case R_RISCV_CALL: {
242       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
243       int64_t Hi = Value + 0x800;
244       if (LLVM_UNLIKELY(!isInRangeForImm(Hi, 32)))
245         return makeTargetOutOfRangeError(G, B, E);
246       int32_t Lo = Value & 0xFFF;
247       uint32_t RawInstrAuipc = *(little32_t *)FixupPtr;
248       uint32_t RawInstrJalr = *(little32_t *)(FixupPtr + 4);
249       *(little32_t *)FixupPtr =
250           RawInstrAuipc | (static_cast<uint32_t>(Hi & 0xFFFFF000));
251       *(little32_t *)(FixupPtr + 4) =
252           RawInstrJalr | (static_cast<uint32_t>(Lo) << 20);
253       break;
254     }
255     // The relocations R_RISCV_CALL_PLT and R_RISCV_GOT_HI20 are handled by
256     // PerGraphGOTAndPLTStubsBuilder_ELF_riscv and are transformed into
257     // R_RISCV_CALL and R_RISCV_PCREL_HI20.
258     case R_RISCV_PCREL_HI20: {
259       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
260       int64_t Hi = Value + 0x800;
261       if (LLVM_UNLIKELY(!isInRangeForImm(Hi, 32)))
262         return makeTargetOutOfRangeError(G, B, E);
263       uint32_t RawInstr = *(little32_t *)FixupPtr;
264       *(little32_t *)FixupPtr =
265           (RawInstr & 0xFFF) | (static_cast<uint32_t>(Hi & 0xFFFFF000));
266       break;
267     }
268     case R_RISCV_PCREL_LO12_I: {
269       // FIXME: We assume that R_RISCV_PCREL_HI20 is present in object code and
270       // pairs with current relocation R_RISCV_PCREL_LO12_I. So here may need a
271       // check.
272       auto RelHI20 = getRISCVPCRelHi20(E);
273       if (!RelHI20)
274         return RelHI20.takeError();
275       int64_t Value = RelHI20->getTarget().getAddress() +
276                       RelHI20->getAddend() - E.getTarget().getAddress();
277       int64_t Lo = Value & 0xFFF;
278       uint32_t RawInstr = *(little32_t *)FixupPtr;
279       *(little32_t *)FixupPtr =
280           (RawInstr & 0xFFFFF) | (static_cast<uint32_t>(Lo & 0xFFF) << 20);
281       break;
282     }
283     case R_RISCV_PCREL_LO12_S: {
284       // FIXME: We assume that R_RISCV_PCREL_HI20 is present in object code and
285       // pairs with current relocation R_RISCV_PCREL_LO12_S. So here may need a
286       // check.
287       auto RelHI20 = getRISCVPCRelHi20(E);
288       if (!RelHI20)
289         return RelHI20.takeError();
290       int64_t Value = RelHI20->getTarget().getAddress() +
291                       RelHI20->getAddend() - E.getTarget().getAddress();
292       int64_t Lo = Value & 0xFFF;
293       uint32_t Imm11_5 = extractBits(Lo, 5, 7) << 25;
294       uint32_t Imm4_0 = extractBits(Lo, 0, 5) << 7;
295       uint32_t RawInstr = *(little32_t *)FixupPtr;
296 
297       *(little32_t *)FixupPtr = (RawInstr & 0x1FFF07F) | Imm11_5 | Imm4_0;
298       break;
299     }
300     case R_RISCV_HI20: {
301       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
302       int64_t Hi = Value + 0x800;
303       if (LLVM_UNLIKELY(!isInRangeForImm(Hi, 32)))
304         return makeTargetOutOfRangeError(G, B, E);
305       uint32_t RawInstr = *(little32_t *)FixupPtr;
306       *(little32_t *)FixupPtr =
307           (RawInstr & 0xFFF) | (static_cast<uint32_t>(Hi & 0xFFFFF000));
308       break;
309     }
310     case R_RISCV_LO12_I: {
311       // FIXME: We assume that R_RISCV_HI20 is present in object code and pairs
312       // with current relocation R_RISCV_LO12_I. So here may need a check.
313       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
314       int32_t Lo = Value & 0xFFF;
315       uint32_t RawInstr = *(little32_t *)FixupPtr;
316       *(little32_t *)FixupPtr =
317           (RawInstr & 0xFFFFF) | (static_cast<uint32_t>(Lo & 0xFFF) << 20);
318       break;
319     }
320     case R_RISCV_LO12_S: {
321       // FIXME: We assume that R_RISCV_HI20 is present in object code and pairs
322       // with current relocation R_RISCV_LO12_S. So here may need a check.
323       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
324       int64_t Lo = Value & 0xFFF;
325       uint32_t Imm11_5 = extractBits(Lo, 5, 7) << 25;
326       uint32_t Imm4_0 = extractBits(Lo, 0, 5) << 7;
327       uint32_t RawInstr = *(little32_t *)FixupPtr;
328       *(little32_t *)FixupPtr = (RawInstr & 0x1FFF07F) | Imm11_5 | Imm4_0;
329       break;
330     }
331     case R_RISCV_ADD8: {
332       int64_t Value =
333           (E.getTarget().getAddress() +
334            *(reinterpret_cast<const uint8_t *>(FixupPtr)) + E.getAddend())
335               .getValue();
336       *FixupPtr = static_cast<uint8_t>(Value);
337       break;
338     }
339     case R_RISCV_ADD16: {
340       int64_t Value = (E.getTarget().getAddress() +
341                        support::endian::read16le(FixupPtr) + E.getAddend())
342                           .getValue();
343       *(little16_t *)FixupPtr = static_cast<uint16_t>(Value);
344       break;
345     }
346     case R_RISCV_ADD32: {
347       int64_t Value = (E.getTarget().getAddress() +
348                        support::endian::read32le(FixupPtr) + E.getAddend())
349                           .getValue();
350       *(little32_t *)FixupPtr = static_cast<uint32_t>(Value);
351       break;
352     }
353     case R_RISCV_ADD64: {
354       int64_t Value = (E.getTarget().getAddress() +
355                        support::endian::read64le(FixupPtr) + E.getAddend())
356                           .getValue();
357       *(little64_t *)FixupPtr = static_cast<uint64_t>(Value);
358       break;
359     }
360     case R_RISCV_SUB8: {
361       int64_t Value = *(reinterpret_cast<const uint8_t *>(FixupPtr)) -
362                       E.getTarget().getAddress().getValue() - E.getAddend();
363       *FixupPtr = static_cast<uint8_t>(Value);
364       break;
365     }
366     case R_RISCV_SUB16: {
367       int64_t Value = support::endian::read16le(FixupPtr) -
368                       E.getTarget().getAddress().getValue() - E.getAddend();
369       *(little16_t *)FixupPtr = static_cast<uint32_t>(Value);
370       break;
371     }
372     case R_RISCV_SUB32: {
373       int64_t Value = support::endian::read32le(FixupPtr) -
374                       E.getTarget().getAddress().getValue() - E.getAddend();
375       *(little32_t *)FixupPtr = static_cast<uint32_t>(Value);
376       break;
377     }
378     case R_RISCV_SUB64: {
379       int64_t Value = support::endian::read64le(FixupPtr) -
380                       E.getTarget().getAddress().getValue() - E.getAddend();
381       *(little64_t *)FixupPtr = static_cast<uint64_t>(Value);
382       break;
383     }
384     case R_RISCV_RVC_BRANCH: {
385       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
386       if (LLVM_UNLIKELY(!isInRangeForImm(Value >> 1, 8)))
387         return makeTargetOutOfRangeError(G, B, E);
388       if (LLVM_UNLIKELY(!isAlignmentCorrect(Value, 2)))
389         return makeAlignmentError(FixupAddress, Value, 2, E);
390       uint16_t Imm8 = extractBits(Value, 8, 1) << 12;
391       uint16_t Imm4_3 = extractBits(Value, 3, 2) << 10;
392       uint16_t Imm7_6 = extractBits(Value, 6, 2) << 5;
393       uint16_t Imm2_1 = extractBits(Value, 1, 2) << 3;
394       uint16_t Imm5 = extractBits(Value, 5, 1) << 2;
395       uint16_t RawInstr = *(little16_t *)FixupPtr;
396       *(little16_t *)FixupPtr =
397           (RawInstr & 0xE383) | Imm8 | Imm4_3 | Imm7_6 | Imm2_1 | Imm5;
398       break;
399     }
400     case R_RISCV_RVC_JUMP: {
401       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
402       if (LLVM_UNLIKELY(!isInRangeForImm(Value >> 1, 11)))
403         return makeTargetOutOfRangeError(G, B, E);
404       if (LLVM_UNLIKELY(!isAlignmentCorrect(Value, 2)))
405         return makeAlignmentError(FixupAddress, Value, 2, E);
406       uint16_t Imm11 = extractBits(Value, 11, 1) << 12;
407       uint16_t Imm4 = extractBits(Value, 4, 1) << 11;
408       uint16_t Imm9_8 = extractBits(Value, 8, 2) << 9;
409       uint16_t Imm10 = extractBits(Value, 10, 1) << 8;
410       uint16_t Imm6 = extractBits(Value, 6, 1) << 7;
411       uint16_t Imm7 = extractBits(Value, 7, 1) << 6;
412       uint16_t Imm3_1 = extractBits(Value, 1, 3) << 3;
413       uint16_t Imm5 = extractBits(Value, 5, 1) << 2;
414       uint16_t RawInstr = *(little16_t *)FixupPtr;
415       *(little16_t *)FixupPtr = (RawInstr & 0xE003) | Imm11 | Imm4 | Imm9_8 |
416                                 Imm10 | Imm6 | Imm7 | Imm3_1 | Imm5;
417       break;
418     }
419     case R_RISCV_SUB6: {
420       int64_t Value = *(reinterpret_cast<const uint8_t *>(FixupPtr)) & 0x3f;
421       Value -= E.getTarget().getAddress().getValue() - E.getAddend();
422       *FixupPtr = (*FixupPtr & 0xc0) | (static_cast<uint8_t>(Value) & 0x3f);
423       break;
424     }
425     case R_RISCV_SET6: {
426       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
427       uint32_t RawData = *(little32_t *)FixupPtr;
428       int64_t Word6 = Value & 0x3f;
429       *(little32_t *)FixupPtr = (RawData & 0xffffffc0) | Word6;
430       break;
431     }
432     case R_RISCV_SET8: {
433       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
434       uint32_t RawData = *(little32_t *)FixupPtr;
435       int64_t Word8 = Value & 0xff;
436       *(little32_t *)FixupPtr = (RawData & 0xffffff00) | Word8;
437       break;
438     }
439     case R_RISCV_SET16: {
440       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
441       uint32_t RawData = *(little32_t *)FixupPtr;
442       int64_t Word16 = Value & 0xffff;
443       *(little32_t *)FixupPtr = (RawData & 0xffff0000) | Word16;
444       break;
445     }
446     case R_RISCV_SET32: {
447       int64_t Value = (E.getTarget().getAddress() + E.getAddend()).getValue();
448       int64_t Word32 = Value & 0xffffffff;
449       *(little32_t *)FixupPtr = Word32;
450       break;
451     }
452     case R_RISCV_32_PCREL: {
453       int64_t Value = E.getTarget().getAddress() + E.getAddend() - FixupAddress;
454       int64_t Word32 = Value & 0xffffffff;
455       *(little32_t *)FixupPtr = Word32;
456       break;
457     }
458     case AlignRelaxable:
459       // Ignore when the relaxation pass did not run
460       break;
461     case NegDelta32: {
462       int64_t Value = FixupAddress - E.getTarget().getAddress() + E.getAddend();
463       if (LLVM_UNLIKELY(!isInRangeForImm(Value, 32)))
464         return makeTargetOutOfRangeError(G, B, E);
465       *(little32_t *)FixupPtr = static_cast<uint32_t>(Value);
466       break;
467     }
468     }
469     return Error::success();
470   }
471 };
472 
473 namespace {
474 
475 struct SymbolAnchor {
476   uint64_t Offset;
477   Symbol *Sym;
478   bool End; // true for the anchor of getOffset() + getSize()
479 };
480 
481 struct BlockRelaxAux {
482   // This records symbol start and end offsets which will be adjusted according
483   // to the nearest RelocDeltas element.
484   SmallVector<SymbolAnchor, 0> Anchors;
485   // All edges that either 1) are R_RISCV_ALIGN or 2) have a R_RISCV_RELAX edge
486   // at the same offset.
487   SmallVector<Edge *, 0> RelaxEdges;
488   // For RelaxEdges[I], the actual offset is RelaxEdges[I]->getOffset() - (I ?
489   // RelocDeltas[I - 1] : 0).
490   SmallVector<uint32_t, 0> RelocDeltas;
491   // For RelaxEdges[I], the actual type is EdgeKinds[I].
492   SmallVector<Edge::Kind, 0> EdgeKinds;
493   // List of rewritten instructions. Contains one raw encoded instruction per
494   // element in EdgeKinds that isn't Invalid or R_RISCV_ALIGN.
495   SmallVector<uint32_t, 0> Writes;
496 };
497 
498 struct RelaxConfig {
499   bool IsRV32;
500   bool HasRVC;
501 };
502 
503 struct RelaxAux {
504   RelaxConfig Config;
505   DenseMap<Block *, BlockRelaxAux> Blocks;
506 };
507 
508 } // namespace
509 
510 static bool shouldRelax(const Section &S) {
511   return (S.getMemProt() & orc::MemProt::Exec) != orc::MemProt::None;
512 }
513 
514 static bool isRelaxable(const Edge &E) {
515   switch (E.getKind()) {
516   default:
517     return false;
518   case CallRelaxable:
519   case AlignRelaxable:
520     return true;
521   }
522 }
523 
524 static RelaxAux initRelaxAux(LinkGraph &G) {
525   RelaxAux Aux;
526   Aux.Config.IsRV32 = G.getTargetTriple().isRISCV32();
527   const auto &Features = G.getFeatures().getFeatures();
528   Aux.Config.HasRVC = llvm::is_contained(Features, "+c") ||
529                       llvm::is_contained(Features, "+zca");
530 
531   for (auto &S : G.sections()) {
532     if (!shouldRelax(S))
533       continue;
534     for (auto *B : S.blocks()) {
535       auto BlockEmplaceResult = Aux.Blocks.try_emplace(B);
536       assert(BlockEmplaceResult.second && "Block encountered twice");
537       auto &BlockAux = BlockEmplaceResult.first->second;
538 
539       for (auto &E : B->edges())
540         if (isRelaxable(E))
541           BlockAux.RelaxEdges.push_back(&E);
542 
543       if (BlockAux.RelaxEdges.empty()) {
544         Aux.Blocks.erase(BlockEmplaceResult.first);
545         continue;
546       }
547 
548       const auto NumEdges = BlockAux.RelaxEdges.size();
549       BlockAux.RelocDeltas.resize(NumEdges, 0);
550       BlockAux.EdgeKinds.resize_for_overwrite(NumEdges);
551 
552       // Store anchors (offset and offset+size) for symbols.
553       for (auto *Sym : S.symbols()) {
554         if (!Sym->isDefined() || &Sym->getBlock() != B)
555           continue;
556 
557         BlockAux.Anchors.push_back({Sym->getOffset(), Sym, false});
558         BlockAux.Anchors.push_back(
559             {Sym->getOffset() + Sym->getSize(), Sym, true});
560       }
561     }
562   }
563 
564   // Sort anchors by offset so that we can find the closest relocation
565   // efficiently. For a zero size symbol, ensure that its start anchor precedes
566   // its end anchor. For two symbols with anchors at the same offset, their
567   // order does not matter.
568   for (auto &BlockAuxIter : Aux.Blocks) {
569     llvm::sort(BlockAuxIter.second.Anchors, [](auto &A, auto &B) {
570       return std::make_pair(A.Offset, A.End) < std::make_pair(B.Offset, B.End);
571     });
572   }
573 
574   return Aux;
575 }
576 
577 static void relaxAlign(orc::ExecutorAddr Loc, const Edge &E, uint32_t &Remove,
578                        Edge::Kind &NewEdgeKind) {
579   // E points to the start of the padding bytes.
580   // E + Addend points to the instruction to be aligned by removing padding.
581   // Alignment is the smallest power of 2 strictly greater than Addend.
582   const auto Align = NextPowerOf2(E.getAddend());
583   const auto DestLoc = alignTo(Loc.getValue(), Align);
584   const auto SrcLoc = Loc.getValue() + E.getAddend();
585   Remove = SrcLoc - DestLoc;
586   assert(static_cast<int32_t>(Remove) >= 0 &&
587          "R_RISCV_ALIGN needs expanding the content");
588   NewEdgeKind = AlignRelaxable;
589 }
590 
591 static void relaxCall(const Block &B, BlockRelaxAux &Aux,
592                       const RelaxConfig &Config, orc::ExecutorAddr Loc,
593                       const Edge &E, uint32_t &Remove,
594                       Edge::Kind &NewEdgeKind) {
595   const auto JALR =
596       support::endian::read32le(B.getContent().data() + E.getOffset() + 4);
597   const auto RD = extractBits(JALR, 7, 5);
598   const auto Dest = E.getTarget().getAddress() + E.getAddend();
599   const auto Displace = Dest - Loc;
600 
601   if (Config.HasRVC && isInt<12>(Displace) && RD == 0) {
602     NewEdgeKind = R_RISCV_RVC_JUMP;
603     Aux.Writes.push_back(0xa001); // c.j
604     Remove = 6;
605   } else if (Config.HasRVC && Config.IsRV32 && isInt<12>(Displace) && RD == 1) {
606     NewEdgeKind = R_RISCV_RVC_JUMP;
607     Aux.Writes.push_back(0x2001); // c.jal
608     Remove = 6;
609   } else if (isInt<21>(Displace)) {
610     NewEdgeKind = R_RISCV_JAL;
611     Aux.Writes.push_back(0x6f | RD << 7); // jal
612     Remove = 4;
613   } else {
614     // Not relaxable
615     NewEdgeKind = R_RISCV_CALL_PLT;
616     Remove = 0;
617   }
618 }
619 
620 static bool relaxBlock(LinkGraph &G, Block &Block, BlockRelaxAux &Aux,
621                        const RelaxConfig &Config) {
622   const auto BlockAddr = Block.getAddress();
623   bool Changed = false;
624   ArrayRef<SymbolAnchor> SA = ArrayRef(Aux.Anchors);
625   uint32_t Delta = 0;
626 
627   Aux.EdgeKinds.assign(Aux.EdgeKinds.size(), Edge::Invalid);
628   Aux.Writes.clear();
629 
630   for (auto [I, E] : llvm::enumerate(Aux.RelaxEdges)) {
631     const auto Loc = BlockAddr + E->getOffset() - Delta;
632     auto &Cur = Aux.RelocDeltas[I];
633     uint32_t Remove = 0;
634     switch (E->getKind()) {
635     case AlignRelaxable:
636       relaxAlign(Loc, *E, Remove, Aux.EdgeKinds[I]);
637       break;
638     case CallRelaxable:
639       relaxCall(Block, Aux, Config, Loc, *E, Remove, Aux.EdgeKinds[I]);
640       break;
641     default:
642       llvm_unreachable("Unexpected relaxable edge kind");
643     }
644 
645     // For all anchors whose offsets are <= E->getOffset(), they are preceded by
646     // the previous relocation whose RelocDeltas value equals Delta.
647     // Decrease their offset and update their size.
648     for (; SA.size() && SA[0].Offset <= E->getOffset(); SA = SA.slice(1)) {
649       if (SA[0].End)
650         SA[0].Sym->setSize(SA[0].Offset - Delta - SA[0].Sym->getOffset());
651       else
652         SA[0].Sym->setOffset(SA[0].Offset - Delta);
653     }
654 
655     Delta += Remove;
656     if (Delta != Cur) {
657       Cur = Delta;
658       Changed = true;
659     }
660   }
661 
662   for (const SymbolAnchor &A : SA) {
663     if (A.End)
664       A.Sym->setSize(A.Offset - Delta - A.Sym->getOffset());
665     else
666       A.Sym->setOffset(A.Offset - Delta);
667   }
668 
669   return Changed;
670 }
671 
672 static bool relaxOnce(LinkGraph &G, RelaxAux &Aux) {
673   bool Changed = false;
674 
675   for (auto &[B, BlockAux] : Aux.Blocks)
676     Changed |= relaxBlock(G, *B, BlockAux, Aux.Config);
677 
678   return Changed;
679 }
680 
681 static void finalizeBlockRelax(LinkGraph &G, Block &Block, BlockRelaxAux &Aux) {
682   auto Contents = Block.getAlreadyMutableContent();
683   auto *Dest = Contents.data();
684   auto NextWrite = Aux.Writes.begin();
685   uint32_t Offset = 0;
686   uint32_t Delta = 0;
687 
688   // Update section content: remove NOPs for R_RISCV_ALIGN and rewrite
689   // instructions for relaxed relocations.
690   for (auto [I, E] : llvm::enumerate(Aux.RelaxEdges)) {
691     uint32_t Remove = Aux.RelocDeltas[I] - Delta;
692     Delta = Aux.RelocDeltas[I];
693     if (Remove == 0 && Aux.EdgeKinds[I] == Edge::Invalid)
694       continue;
695 
696     // Copy from last location to the current relocated location.
697     const auto Size = E->getOffset() - Offset;
698     std::memmove(Dest, Contents.data() + Offset, Size);
699     Dest += Size;
700 
701     uint32_t Skip = 0;
702     switch (Aux.EdgeKinds[I]) {
703     case Edge::Invalid:
704       break;
705     case AlignRelaxable:
706       // For R_RISCV_ALIGN, we will place Offset in a location (among NOPs) to
707       // satisfy the alignment requirement. If both Remove and E->getAddend()
708       // are multiples of 4, it is as if we have skipped some NOPs. Otherwise we
709       // are in the middle of a 4-byte NOP, and we need to rewrite the NOP
710       // sequence.
711       if (Remove % 4 || E->getAddend() % 4) {
712         Skip = E->getAddend() - Remove;
713         uint32_t J = 0;
714         for (; J + 4 <= Skip; J += 4)
715           support::endian::write32le(Dest + J, 0x00000013); // nop
716         if (J != Skip) {
717           assert(J + 2 == Skip);
718           support::endian::write16le(Dest + J, 0x0001); // c.nop
719         }
720       }
721       break;
722     case R_RISCV_RVC_JUMP:
723       Skip = 2;
724       support::endian::write16le(Dest, *NextWrite++);
725       break;
726     case R_RISCV_JAL:
727       Skip = 4;
728       support::endian::write32le(Dest, *NextWrite++);
729       break;
730     }
731 
732     Dest += Skip;
733     Offset = E->getOffset() + Skip + Remove;
734   }
735 
736   std::memmove(Dest, Contents.data() + Offset, Contents.size() - Offset);
737 
738   // Fixup edge offsets and kinds.
739   Delta = 0;
740   size_t I = 0;
741   for (auto &E : Block.edges()) {
742     E.setOffset(E.getOffset() - Delta);
743 
744     if (I < Aux.RelaxEdges.size() && Aux.RelaxEdges[I] == &E) {
745       if (Aux.EdgeKinds[I] != Edge::Invalid)
746         E.setKind(Aux.EdgeKinds[I]);
747 
748       Delta = Aux.RelocDeltas[I];
749       ++I;
750     }
751   }
752 
753   // Remove AlignRelaxable edges: all other relaxable edges got modified and
754   // will be used later while linking. Alignment is entirely handled here so we
755   // don't need these edges anymore.
756   for (auto IE = Block.edges().begin(); IE != Block.edges().end();) {
757     if (IE->getKind() == AlignRelaxable)
758       IE = Block.removeEdge(IE);
759     else
760       ++IE;
761   }
762 }
763 
764 static void finalizeRelax(LinkGraph &G, RelaxAux &Aux) {
765   for (auto &[B, BlockAux] : Aux.Blocks)
766     finalizeBlockRelax(G, *B, BlockAux);
767 }
768 
769 static Error relax(LinkGraph &G) {
770   auto Aux = initRelaxAux(G);
771   while (relaxOnce(G, Aux)) {
772   }
773   finalizeRelax(G, Aux);
774   return Error::success();
775 }
776 
777 template <typename ELFT>
778 class ELFLinkGraphBuilder_riscv : public ELFLinkGraphBuilder<ELFT> {
779 private:
780   static Expected<riscv::EdgeKind_riscv>
781   getRelocationKind(const uint32_t Type) {
782     using namespace riscv;
783     switch (Type) {
784     case ELF::R_RISCV_32:
785       return EdgeKind_riscv::R_RISCV_32;
786     case ELF::R_RISCV_64:
787       return EdgeKind_riscv::R_RISCV_64;
788     case ELF::R_RISCV_BRANCH:
789       return EdgeKind_riscv::R_RISCV_BRANCH;
790     case ELF::R_RISCV_JAL:
791       return EdgeKind_riscv::R_RISCV_JAL;
792     case ELF::R_RISCV_CALL:
793       return EdgeKind_riscv::R_RISCV_CALL;
794     case ELF::R_RISCV_CALL_PLT:
795       return EdgeKind_riscv::R_RISCV_CALL_PLT;
796     case ELF::R_RISCV_GOT_HI20:
797       return EdgeKind_riscv::R_RISCV_GOT_HI20;
798     case ELF::R_RISCV_PCREL_HI20:
799       return EdgeKind_riscv::R_RISCV_PCREL_HI20;
800     case ELF::R_RISCV_PCREL_LO12_I:
801       return EdgeKind_riscv::R_RISCV_PCREL_LO12_I;
802     case ELF::R_RISCV_PCREL_LO12_S:
803       return EdgeKind_riscv::R_RISCV_PCREL_LO12_S;
804     case ELF::R_RISCV_HI20:
805       return EdgeKind_riscv::R_RISCV_HI20;
806     case ELF::R_RISCV_LO12_I:
807       return EdgeKind_riscv::R_RISCV_LO12_I;
808     case ELF::R_RISCV_LO12_S:
809       return EdgeKind_riscv::R_RISCV_LO12_S;
810     case ELF::R_RISCV_ADD8:
811       return EdgeKind_riscv::R_RISCV_ADD8;
812     case ELF::R_RISCV_ADD16:
813       return EdgeKind_riscv::R_RISCV_ADD16;
814     case ELF::R_RISCV_ADD32:
815       return EdgeKind_riscv::R_RISCV_ADD32;
816     case ELF::R_RISCV_ADD64:
817       return EdgeKind_riscv::R_RISCV_ADD64;
818     case ELF::R_RISCV_SUB8:
819       return EdgeKind_riscv::R_RISCV_SUB8;
820     case ELF::R_RISCV_SUB16:
821       return EdgeKind_riscv::R_RISCV_SUB16;
822     case ELF::R_RISCV_SUB32:
823       return EdgeKind_riscv::R_RISCV_SUB32;
824     case ELF::R_RISCV_SUB64:
825       return EdgeKind_riscv::R_RISCV_SUB64;
826     case ELF::R_RISCV_RVC_BRANCH:
827       return EdgeKind_riscv::R_RISCV_RVC_BRANCH;
828     case ELF::R_RISCV_RVC_JUMP:
829       return EdgeKind_riscv::R_RISCV_RVC_JUMP;
830     case ELF::R_RISCV_SUB6:
831       return EdgeKind_riscv::R_RISCV_SUB6;
832     case ELF::R_RISCV_SET6:
833       return EdgeKind_riscv::R_RISCV_SET6;
834     case ELF::R_RISCV_SET8:
835       return EdgeKind_riscv::R_RISCV_SET8;
836     case ELF::R_RISCV_SET16:
837       return EdgeKind_riscv::R_RISCV_SET16;
838     case ELF::R_RISCV_SET32:
839       return EdgeKind_riscv::R_RISCV_SET32;
840     case ELF::R_RISCV_32_PCREL:
841       return EdgeKind_riscv::R_RISCV_32_PCREL;
842     case ELF::R_RISCV_ALIGN:
843       return EdgeKind_riscv::AlignRelaxable;
844     }
845 
846     return make_error<JITLinkError>(
847         "Unsupported riscv relocation:" + formatv("{0:d}: ", Type) +
848         object::getELFRelocationTypeName(ELF::EM_RISCV, Type));
849   }
850 
851   EdgeKind_riscv getRelaxableRelocationKind(EdgeKind_riscv Kind) {
852     switch (Kind) {
853     default:
854       // Just ignore unsupported relaxations
855       return Kind;
856     case R_RISCV_CALL:
857     case R_RISCV_CALL_PLT:
858       return CallRelaxable;
859     }
860   }
861 
862   Error addRelocations() override {
863     LLVM_DEBUG(dbgs() << "Processing relocations:\n");
864 
865     using Base = ELFLinkGraphBuilder<ELFT>;
866     using Self = ELFLinkGraphBuilder_riscv<ELFT>;
867     for (const auto &RelSect : Base::Sections)
868       if (Error Err = Base::forEachRelaRelocation(RelSect, this,
869                                                   &Self::addSingleRelocation))
870         return Err;
871 
872     return Error::success();
873   }
874 
875   Error addSingleRelocation(const typename ELFT::Rela &Rel,
876                             const typename ELFT::Shdr &FixupSect,
877                             Block &BlockToFix) {
878     using Base = ELFLinkGraphBuilder<ELFT>;
879 
880     uint32_t Type = Rel.getType(false);
881     int64_t Addend = Rel.r_addend;
882 
883     if (Type == ELF::R_RISCV_RELAX) {
884       if (BlockToFix.edges_empty())
885         return make_error<StringError>(
886             "R_RISCV_RELAX without preceding relocation",
887             inconvertibleErrorCode());
888 
889       auto &PrevEdge = *std::prev(BlockToFix.edges().end());
890       auto Kind = static_cast<EdgeKind_riscv>(PrevEdge.getKind());
891       PrevEdge.setKind(getRelaxableRelocationKind(Kind));
892       return Error::success();
893     }
894 
895     Expected<riscv::EdgeKind_riscv> Kind = getRelocationKind(Type);
896     if (!Kind)
897       return Kind.takeError();
898 
899     uint32_t SymbolIndex = Rel.getSymbol(false);
900     auto ObjSymbol = Base::Obj.getRelocationSymbol(Rel, Base::SymTabSec);
901     if (!ObjSymbol)
902       return ObjSymbol.takeError();
903 
904     Symbol *GraphSymbol = Base::getGraphSymbol(SymbolIndex);
905     if (!GraphSymbol)
906       return make_error<StringError>(
907           formatv("Could not find symbol at given index, did you add it to "
908                   "JITSymbolTable? index: {0}, shndx: {1} Size of table: {2}",
909                   SymbolIndex, (*ObjSymbol)->st_shndx,
910                   Base::GraphSymbols.size()),
911           inconvertibleErrorCode());
912 
913     auto FixupAddress = orc::ExecutorAddr(FixupSect.sh_addr) + Rel.r_offset;
914     Edge::OffsetT Offset = FixupAddress - BlockToFix.getAddress();
915     Edge GE(*Kind, Offset, *GraphSymbol, Addend);
916     LLVM_DEBUG({
917       dbgs() << "    ";
918       printEdge(dbgs(), BlockToFix, GE, riscv::getEdgeKindName(*Kind));
919       dbgs() << "\n";
920     });
921 
922     BlockToFix.addEdge(std::move(GE));
923     return Error::success();
924   }
925 
926 public:
927   ELFLinkGraphBuilder_riscv(StringRef FileName,
928                             const object::ELFFile<ELFT> &Obj, Triple TT,
929                             SubtargetFeatures Features)
930       : ELFLinkGraphBuilder<ELFT>(Obj, std::move(TT), std::move(Features),
931                                   FileName, riscv::getEdgeKindName) {}
932 };
933 
934 Expected<std::unique_ptr<LinkGraph>>
935 createLinkGraphFromELFObject_riscv(MemoryBufferRef ObjectBuffer) {
936   LLVM_DEBUG({
937     dbgs() << "Building jitlink graph for new input "
938            << ObjectBuffer.getBufferIdentifier() << "...\n";
939   });
940 
941   auto ELFObj = object::ObjectFile::createELFObjectFile(ObjectBuffer);
942   if (!ELFObj)
943     return ELFObj.takeError();
944 
945   auto Features = (*ELFObj)->getFeatures();
946   if (!Features)
947     return Features.takeError();
948 
949   if ((*ELFObj)->getArch() == Triple::riscv64) {
950     auto &ELFObjFile = cast<object::ELFObjectFile<object::ELF64LE>>(**ELFObj);
951     return ELFLinkGraphBuilder_riscv<object::ELF64LE>(
952                (*ELFObj)->getFileName(), ELFObjFile.getELFFile(),
953                (*ELFObj)->makeTriple(), std::move(*Features))
954         .buildGraph();
955   } else {
956     assert((*ELFObj)->getArch() == Triple::riscv32 &&
957            "Invalid triple for RISCV ELF object file");
958     auto &ELFObjFile = cast<object::ELFObjectFile<object::ELF32LE>>(**ELFObj);
959     return ELFLinkGraphBuilder_riscv<object::ELF32LE>(
960                (*ELFObj)->getFileName(), ELFObjFile.getELFFile(),
961                (*ELFObj)->makeTriple(), std::move(*Features))
962         .buildGraph();
963   }
964 }
965 
966 void link_ELF_riscv(std::unique_ptr<LinkGraph> G,
967                     std::unique_ptr<JITLinkContext> Ctx) {
968   PassConfiguration Config;
969   const Triple &TT = G->getTargetTriple();
970   if (Ctx->shouldAddDefaultTargetPasses(TT)) {
971 
972     Config.PrePrunePasses.push_back(DWARFRecordSectionSplitter(".eh_frame"));
973     Config.PrePrunePasses.push_back(EHFrameEdgeFixer(
974         ".eh_frame", G->getPointerSize(), Edge::Invalid, Edge::Invalid,
975         Edge::Invalid, Edge::Invalid, NegDelta32));
976     Config.PrePrunePasses.push_back(EHFrameNullTerminator(".eh_frame"));
977 
978     if (auto MarkLive = Ctx->getMarkLivePass(TT))
979       Config.PrePrunePasses.push_back(std::move(MarkLive));
980     else
981       Config.PrePrunePasses.push_back(markAllSymbolsLive);
982     Config.PostPrunePasses.push_back(
983         PerGraphGOTAndPLTStubsBuilder_ELF_riscv::asPass);
984     Config.PostAllocationPasses.push_back(relax);
985   }
986   if (auto Err = Ctx->modifyPassConfig(*G, Config))
987     return Ctx->notifyFailed(std::move(Err));
988 
989   ELFJITLinker_riscv::link(std::move(Ctx), std::move(G), std::move(Config));
990 }
991 
992 LinkGraphPassFunction createRelaxationPass_ELF_riscv() { return relax; }
993 
994 } // namespace jitlink
995 } // namespace llvm
996