[lld] Support RISC-V
ClosedPublic

Authored by PkmX on Oct 26 2017, 1:24 AM.

Details

Summary

This patch makes lld recognize RISC-V target and implements basic relocation for RV32/RV64 (and RVC). This should be necessary for static linking ELF applications.

The ABI documentation for RISC-V can be found at: https://github.com/riscv/riscv-elf-psabi-doc/blob/master/riscv-elf.md. Note that the documentation is far from complete so we had to figure out some details from bfd.

The patch should be pretty straightforward. Some highlights:

  • A new relocation Expr R_RISCV_PC_INDIRECT is added. This is needed as the low part of a PC-relative relocation is linked to the corresponding high part (auipc), see: https://github.com/riscv/riscv-elf-psabi-doc/blob/master/riscv-elf.md#pc-relative-symbol-addresses
  • LLVM's MC support for RISC-V is very incomplete (we are working on this), so tests are given in objectyaml format with the original assembly included in the comments. Once we have complete support for RISC-V in MC, we can switch to llvm-as/llvm-objdump.
  • We don't support linker relaxation for now as it requires greater changes to lld that is beyond the scope of this patch. Once this is accepted we can start to work on adding relaxation to lld.

Diff Detail

Repository
rL LLVM
There are a very large number of changes, so older changes are hidden. Show Older Changes
ruiu added inline comments.Oct 26 2017, 1:14 PM
ELF/Target.cpp
76–93 ↗(On Diff #120366)

Sort

82–89 ↗(On Diff #120366)

Big-endian RISC-Vs seems unreachable. I'd remove them if it is not needed now.

ELF/Target.h
123–131 ↗(On Diff #120366)

Sort

(Basically, we want to add new code to the place where it would have been if it had existed from beginning. This makes our code look less patch-y.)

ELF/Writer.cpp
782–783 ↗(On Diff #120366)

Needs comment.

954–960 ↗(On Diff #120366)

Format

PkmX marked 12 inline comments as done.Oct 26 2017, 7:49 PM
In D39322#908393, @ruiu wrote:

As you said this looks like a pretty straightforward port to RISC-V. Thank you for doing this!

IIRC, last time when we discussed RISC-V support in lld, I had a concern that linker relaxation (moving code inside a section to make it compact) is virtually mandatory to link RISC-V object files. What is the situation of it? If you can link a small static executable with this patch, then it is probably no longer mandatory, but I want to make sure that that's the case.

Yes, linker relaxation is no longer mandatory, after these followup discussion here:
https://github.com/riscv/riscv-binutils-gdb/pull/88
https://github.com/riscv/riscv-tools/issues/132

ELF/Arch/RISCV.cpp
90 ↗(On Diff #120366)

Yes, basically it extracts the bits from [Begin, End] and shifts the result so the LSB is at LShift bit.

Making the range half-open does make it work more like C++ iterators, but it does make cross-referencing with the ISA spec more difficult as ranges are often given in closed forms, e.g. Inst[5:0] means the lowest 6 bits.

I agree we can move the left shift out of the function, and I will also rename the function to extractBits.

293–296 ↗(On Diff #120366)

I don't think there are any big-endian implementations (and the toolchain/libraries are most likely not intensively tested for BE), so yeah I'm going to remove these.

ELF/Symbols.h
346–353 ↗(On Diff #120366)

RISCVGlobalPointer should be the last one in alphabetical order, no?

ELF/Target.cpp
76–93 ↗(On Diff #120366)

It is already in alphabetical order.

ruiu added inline comments.Oct 26 2017, 8:51 PM
ELF/Arch/RISCV.cpp
90 ↗(On Diff #120366)

If it is consistent with the specification, I'm fine with open interval.

PkmX updated this revision to Diff 120541.Oct 26 2017, 11:37 PM
PkmX marked 6 inline comments as done.
ruiu added inline comments.Oct 26 2017, 11:46 PM
ELF/Arch/RISCV.cpp
293–296 ↗(On Diff #120366)

Thanks!

Then maybe it makes more sense if you provide two functions, getRISCV32TargetInfo and getRISCV64TargetInfo, I guess?

44 ↗(On Diff #120541)

This is where you should use RelType too.

86 ↗(On Diff #120541)

I'd replace static_cast<uint64_t>(1) with 1u, as we assume int is at least 32 bits.

PkmX updated this revision to Diff 120794.Oct 30 2017, 4:24 AM
  • Renamed uint32_t to RelType.
  • Detemplate the RISCV class.
ruiu added a comment.Oct 30 2017, 1:29 PM

Generally looking pretty good except lo12 relocations.

ELF/Arch/RISCV.cpp
49–54 ↗(On Diff #120794)

Please remove this function and directly use write32le (I believe instead of calling write16le twice, you can use write32le.).

56–58 ↗(On Diff #120794)

Ditto -- please use read32le directly.

84 ↗(On Diff #120794)

static_cast<uint64_t>(1) -> (uint64_t)1 or 1ULL

as it is obvious that it is a static cast.

ELF/InputSection.cpp
575–582 ↗(On Diff #120794)

It is O(n^2), isn't it? It doesn't seems good.

Fundamentally I think I don't understand why R_RISCV_PCREL_LO12{I,S} were designed that way. IIUC, they are relocations to load a PC-relative symbol address and used in combination with PC_RISCV_PCREL_HI20. A pair of HI and LO relocations are associated via label locations. That seems unnecessarily tricky to me.

The spec says that they are computed this way:

hi20 = ((symbol_address - hi20_reloc_offset + 0x800) >> 12);
lo12 = symbol_address - hi20_reloc_offset - hi20;

but why can't we define lo12 as a more regular relocation like this:

hi20 = ((symbol_address - hi20_reloc_offset + 0x800) >> 12);
lo12 = symbol_address - lo20_reloc_offset - ((symbol_address - lo20_reloc_offset + 0x800 + Addend) >> 12) + Addend;

and set a relocation addend to a distance between a lo12 relocation and a hi12 relocation? This way, you don't really have to associate two relocation, but you can just compute their values separately. What am I missing?

PkmX updated this revision to Diff 120939.Oct 30 2017, 11:52 PM
PkmX marked 3 inline comments as done.
  • Use {read,write}32le to read/write insturctions.
  • Make __global_pointer$ non-absolute.
asb added a comment.Oct 31 2017, 2:49 AM

I'm not an LLD expert, but the RISC-V bits seem correct as far as I can see. I've just added a couple of minor comments.

ELF/Arch/RISCV.cpp
71 ↗(On Diff #120939)

A comment that clarifies the semantics would be useful. Perhaps "Begin and End are inclusive, e.g. extractBits(V, 0, 5) will return the lower 6 bits."

165 ↗(On Diff #120939)

It would seem consistent with the other cases do define Imm* local variables to help piece together the final instruction. It's slightly more verbose, but enforcing uniformity across the cases might make this slightly easier to read?

niosHD added a subscriber: niosHD.Oct 31 2017, 8:11 AM
ruiu added a comment.Oct 31 2017, 4:01 PM

What do you think of lo20 relocations? If there's a better place to ask about the design of the RISC-V ABI, please let me know so that I can start a thread.

PkmX marked an inline comment as done.Oct 31 2017, 5:24 PM

I believe the best place would be either the issue tracker on the psABI doc, or RISC-V's sw-dev mailing list.

ELF/Arch/RISCV.cpp
71 ↗(On Diff #120939)

Will do.

165 ↗(On Diff #120939)

That sounds reasonable. The other cases are more complicated as the Imm needs to be split up and shifted into the correct bit position and or'ed together. With auipc (U-Type) and jalr (I-Type), the imm fields in the instruction are already packed in the right order, so we only need a simple mask and shift.

Actually, for R_RISCV_CALL, I think I should just recursively call relocateOne with R_RISCV_PCREL_HI20 at Buf and R_RISCV_PCREL_LO12_I at Buf + 4 to remove redundant code. This should be okay since we aren't doing relaxation for now.

109 ↗(On Diff #120366)

The cast is needed: consider uint64_t Val = -1, right-shifting an unsigned integer in C performs zero-extension in the MSB and produces a large positive number if interpreted as signed later.

I've removed redundant casts in other checkInt where no shifting is performed.

293–296 ↗(On Diff #120366)

I think it should actually be possible to de-template the class and just use Config->Wordsize and Config->Endianness, then we can just provide a single instance.

86 ↗(On Diff #120541)

On common systems where int is 32-bit (x86_64) and with Begin == 31, 1u << 32 would invoke undefined behavior.

With that said, this will still break if Begin == 63, so I think it is more correct to right-shift from UINT64_MAX.

ELF/Driver.cpp
118–132 ↗(On Diff #120366)

Sorting this alphabetically will put elf32lriscv awkwardly between elf32btsmip and elf32ltsmip, so I think it's better to put it after these two?

.Cases("elf32btsmip", "elf32btsmipn32", {ELF32BEKind, EM_MIPS})                                                                                                                      
.Cases("elf32ltsmip", "elf32ltsmipn32", {ELF32LEKind, EM_MIPS})        
.Case("elf32lriscv", {ELF32LEKind, EM_RISCV})                          
.Case("elf32ppc", {ELF32BEKind, EM_PPC})                               
.Case("elf64btsmip", {ELF64BEKind, EM_MIPS})                           
.Case("elf64ltsmip", {ELF64LEKind, EM_MIPS})                           
.Case("elf64lriscv", {ELF64LEKind, EM_RISCV})
ELF/InputSection.cpp
575–582 ↗(On Diff #120794)

RISC-V expects linker relaxation so the distance between a pair of HI20 and LO12 relocation isn't static. If some code is removed then you need to update the addend of the LO12 of all HI/LO pairs surrounding that change.

It should be possible to pre-compute a mapping from symbols to relocations to reduce the search time complexity, but I think that could go in another patch?

575 ↗(On Diff #120366)

I don't think that should ever happen since the symbol should point to an auipc instruction somewhere in a text section.

ruiu added inline comments.Oct 31 2017, 5:36 PM
ELF/InputSection.cpp
575–582 ↗(On Diff #120794)

Yeah, I guessed that that might be reason. But, if the linker relaxes and repacks instructions, it naturally knows how many bytes have been removed between any two locations, so it can easily compute how many bytes need to be adjusted for lo20 addends, right? I'd think computing the same value using labels is unnecessarily complicated, and it seems like a residue of when the code shrinking relaxation was mandatory for RISC-V.

PkmX updated this revision to Diff 121106.Nov 1 2017, 1:46 AM
PkmX marked an inline comment as done.

Make R_RISCV_CALL reuse R_RISCV_PCREL_HI20 and R_RISCV_PCREL_LO12_I.

PkmX updated this revision to Diff 121837.Nov 6 2017, 11:12 PM
  • Rebase onto latest master
  • Clean up #includes
Razer6 added a subscriber: Razer6.Nov 7 2017, 12:14 AM
ruiu added inline comments.Nov 8 2017, 4:03 PM
ELF/InputSection.cpp
575–582 ↗(On Diff #120794)

I still have a concern on HI20 and LO20 relocations. Could you start a thread to discuss whether it can be fixed in the ABI?

mgrang added a subscriber: mgrang.Nov 17 2017, 11:11 AM
PkmX added a comment.Dec 7 2017, 3:19 AM

Oops. It looks like I actually didn't submit some of these draft comments.

ELF/Arch/RISCV.cpp
10–27 ↗(On Diff #121106)

I think some #includes here are only needed in the subsequent patches and some are simply unnecessary. Noting in case I forget to revise this.

ELF/InputSection.cpp
575–582 ↗(On Diff #120794)

Yeah, that sounds workable. This does mean that the linker needs scan the whole section for LO12 to update the addend during relaxation, as the HI20/LO12 pair may be far apart (it is also perfectly fine for many PCREL_LO12 relocations to refer to the same PCREL_HI20). I'm not sure how this compares performance-wise with storing a label since you only pay for the penalty when you want the value or to find the linked PCREL_HI20.

With that said, I think it may be too late to change the ABI, especially when it comes to a fundamental change like this.

575–582 ↗(On Diff #120794)

BTW, those are called LO12, not LO20.

575–582 ↗(On Diff #120794)

FYI, I've opened a follow-up thread on RISC-V's mailing list:

https://groups.google.com/a/groups.riscv.org/forum/#!topic/sw-dev/IqYjXvl4o4Q

575–582 ↗(On Diff #120794)

FYI, I've opened a follow-up thread on RISC-V's mailing list:

https://groups.google.com/a/groups.riscv.org/forum/#!topic/sw-dev/IqYjXvl4o4Q

575–582 ↗(On Diff #120794)

It's been a while and I don't think they are willing to change the ABI at this point. Do you have further comments and is there still anything that needs to be done with this patch?

xiangzhai added a subscriber: xiangzhai.EditedDec 19 2017, 6:56 PM

Hi Chen,

I believe the best place would be either the issue tracker on the psABI doc, or RISC-V's sw-dev mailing list.

It is a good news that RISCV's ABI document is open! it doesn't like AVR target, I have to borrow code from bintuils because it is difficult to guess ELF Relocation Records Calculation Formula, take AMDGPU for an instance http://llvm.org/docs/AMDGPUUsage.html#relocation-records it is Magic Number to me without ABI document.
I need to learn RISCV ISA and ABI documents, and Chen's great work for LLD and bintuils, because RISCV is more complex than AVR, it needs to implement GOT, PLT, TLS, Trunks, I haven't experienced.

Rui is a nice teacher who reviewed my patch carefully and patiently, it took up his rest time:

朝の8時半から試験っていうのは慌ただしい。昼の会社のソファーでちょっと寝てしまった。やや寝不足。

I experienced a lack of sleep discomfort, it feels really bad! so my sincere thanks will goto LLD leader - Rui ありがとうございました!

Regards,
Leslie Zhai

PkmX updated this revision to Diff 127855.Dec 21 2017, 3:21 AM

Rebase onto latest master.

Rui, is there anything else that is still blocking this patch?

Is there anything missing to land in upstream?

PkmX updated this revision to Diff 133979.Feb 12 2018, 7:32 PM

Rebase onto master.

Is there still anything that needs to be done before this patch can be accepted?

Razer6 added inline comments.Feb 23 2018, 8:18 AM
ELF/Arch/RISCV.cpp
141 ↗(On Diff #133979)

This check should be treated as unsigned (checkUInt<32>) since it is an absolute address.

149 ↗(On Diff #133979)

checkUInt<32> as above

156 ↗(On Diff #133979)

checkUInt<32> as above

164 ↗(On Diff #133979)

checkUInt<32> as above

PkmX added inline comments.Aug 2 2018, 7:47 PM
ELF/Arch/RISCV.cpp
141 ↗(On Diff #133979)

The range of R_RISCV_CALL is signed 32-bit (± 2GiB), so checkInt<32> is indeed correct here.

149 ↗(On Diff #133979)

R_RISCV_HI20 can also address the negative 2 GiB (0xffffffff80000000 to 0xffffffffffffffff) in RV64, so the use checkInt<32> is still correct here.

156 ↗(On Diff #133979)

See above.

164 ↗(On Diff #133979)

See above.

PkmX updated this revision to Diff 158925.Aug 2 2018, 11:46 PM

Hello,

I've rebased the diff to latest trunk again. Some notable differences from last revision:

  • For RISC-V, relocations are sorted by offset target after they have been inserted in scanRelocs, and we use std::equal_range to binary search for R_RISCV_PCREL_HI20. I did some profiling using lld to link RISC-V's Linux kernel and it only spends less than 2% of time in getRISCVPCRelHi20, so it should be fast enough without changing the ABI.
  • RISCV::calcEFlags() is now implemented (docs). The RVC flag is set if any of the object has it set, and the float ABI and RVE flags must be the same across all inputs.
  • __global_pointer$ is now set to .sdata + 0x800 only if it is not already defined by --defsym or from the linker script.

@ruiu what do you suggest as the next step here?

ruiu added a comment.Aug 6 2018, 3:39 PM

Apologies for my belated response. I think this patch is generally looking good. One thing I'd fix before submitting is to rewrite a test using assembly. We do not usually use YAML file for testing. Is there any reason you needed to write them in YAML?

ELF/Relocations.h
132 ↗(On Diff #158925)

Do you really need this abstraction? I'd write a lambda in-place rather than defining a new struct for three two different types of comparisons.

ELF/Symbols.h
335 ↗(On Diff #158925)

nit: add a blank line.

PkmX added a comment.Aug 6 2018, 7:26 PM

Apologies for my belated response. I think this patch is generally looking good. One thing I'd fix before submitting is to rewrite a test using assembly. We do not usually use YAML file for testing. Is there any reason you needed to write them in YAML?

These tests were written in ObjectYAML format since LLVM MC support was very incomplete for RISC-V, and the latest llvm-mc from trunk still cannot assemble these tests correctly due to lack of addend handling. I did include the original assembly text in the tests so once the LLVM port is upstreamed we can just swap it to run assembler proper.

ELF/Relocations.h
132 ↗(On Diff #158925)

You need all these overloads to do heterogeneous comparison in C++ (call std::equal_range on a Relocation vector to find the range equal to an uint64_t offset). You can't use lambdas in-place since they can't be overloaded without some hackery.

ELF/Symbols.h
335 ↗(On Diff #158925)

Will do.

ruiu accepted this revision.Aug 7 2018, 11:27 AM

LGTM

These tests were written in ObjectYAML format since LLVM MC support was very incomplete for RISC-V, and the latest llvm-mc from trunk still cannot assemble these tests correctly due to lack of addend handling. I did include the original assembly text in the tests so once the LLVM port is upstreamed we can just swap it to run assembler proper.

Yeah, we might have discussed this earlier. Sorry for bringing it up again.

This revision is now accepted and ready to land.Aug 7 2018, 11:27 AM
PkmX updated this revision to Diff 159639.Aug 7 2018, 7:15 PM

@ruiu I've uploaded a new patch that adds the blank line to RISCVGlobalPointer as requested. As I do not have commit rights to the LLD repository, could you commit the patch if there are no last-minute issues.

Thanks to all for the review and comments.

Closed by commit rL339364: Support RISC-V (authored by ruiu, committed by ). · Explain WhyAug 9 2018, 11:00 AM
This revision was automatically updated to reflect the committed changes.