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