[RISCV][LLD] Add RISCV zcmt optimise in linker relaxation

[VincentWu]

Summary

This patch implements optimizations for the zcmt extension in lld.

A new TableJumpSectio has been added.

Scans each R_RISCV_CALL/R_RISCV_CALL_PLT relocType in each section before the linker relaxation, recording the name of the symbol.

In finalizeContents the recorded symbol names are sorted in descending order by the number of jumps.

Optimise and insert a new cm.jt/cm.jalt during the relax process. in the process, we reused the`R_RISCV_JAL` relocType

co-author: @ScottEgerton

[kito-cheng]

I think this should really write a psABI spec proposal first.

lld/ELF/Arch/RISCV.cpp

673

This relaxation type remove 6 byte, so this should has higher priority than R_RISCV_CALL/R_RISCV_CALL_PLT to jal?

lld/ELF/SyntheticSections.cpp

1165 ↗

(On Diff #462714)

Should be SHT_PROGBITS, SHT_RISCV_ATTRIBUTES is only used for .riscv.attribute.

1188–1192 ↗

(On Diff #462714)

This should be enough.

1273–1287 ↗

(On Diff #462714)

Hmm, how do you deal with more than one local symbol with same name?

e.g.
Following example has 2 different bar:

foo1.c

static int bar (){return 1;}

int foo1(){return bar();}

foo2.c

static int bar (){return 2;}

int foo2(){return bar();}

main.c

int foo1();
int foo2();
int main(){return foo1()+foo2();}

lld/ELF/SyntheticSections.h

380

addCMJTEntryCandidate/getaddCMJTEntryIndex, and same for addEntryZero/getEntryZero

403

entriesZero -> CMJTEntryCandidates
finalizedEntriesZero -> finalizedCMJTEntries
and same for entriesRa/finalizedEntriesRa.

We only need to record symbol name for finalEntries, so std::vector<std::string> is enough?

410

CMJTEntry/CMJALTEntry rather than Zero/Ra, e.g. maxCMJTEntrySize/maxCMJALTEntrySize, startCMJTEntryIdx/startCMJALTEntryIdx.

lld/ELF/Writer.cpp

457

newlib's implementation using __tbljalvec_base$? and maybe use STB_GLOBAL like __global_pointer$?

https://github.com/linsinan1995/riscv-glibc/commit/5d2e0376316f64acfc047dc3e29fd266a456fb8f

[VincentWu]

address part of comments

lld/ELF/SyntheticSections.cpp

1237 ↗

(On Diff #462714)

We only need to record symbol name for finalEntries, so std::vector<std::string> is enough?

yep but we need sort it in descending order by the number of jumps.
it will be spand more linking time to copy again.

so I chose memory space instead of time.

did you mean it is acceptable if i spend more time to copy it again?

[sinan]

lld/ELF/SyntheticSections.cpp

1165 ↗

(On Diff #462882)

SHF_ALLOC | SHF_EXECINSTR is more appropriate IMO
(https://github.com/riscv/riscv-code-size-reduction/blob/main/Zc-specification/tablejump.adoc#table-jump-fault-handling)

[craig.topper]

lld/ELF/Options.td

324

RISCV-> RISC-V

[MaskRay]

lld/ELF/Options.td

323

FF: we require that new options must start with --, not -

lld/ELF/SyntheticSections.cpp

1164 ↗

(On Diff #462882)

The implementation should be moved to Arch/RISCV.cpp to avoid redundant virtual functions in TargetInfo.

lld/ELF/SyntheticSections.h

32

This is inefficient. If DenseMap<CachedStringRef, ...> works, prefer it.

[jrtc27]

We have the RISC-V attributes section, you should use that (and --(no-)relax) to determine whether or not to use Zcmt relaxation, not invent some new flag, especially since compiler drivers can't use it unless they're sure the linker supports that new flag (think Clang + binutils as the common case where it's hard to know for sure; at least with LLD the likelihood is it's not older than the Clang version, especially in the embedded space) or you require users to opt-in at link time to the relaxation.

[jrtc27]

lld/ELF/Arch/RISCV.cpp

391

This seems wrong

899

This seems like poor design, you shouldn't be using R_RISCV_JAL once it's no longer a JAL instruction there

lld/ELF/SyntheticSections.cpp

1213 ↗

(On Diff #462882)

When moving this to RISCV.cpp please use extractBits

lld/ELF/Writer.cpp

1652

Why isn't this done when we read in the relocations the first time?

2905

Huh? This doesn't make any sense? You're just writing the jump table section on top of every SHF_ALLOC output section? Make it act like every single other synthetic section and end up in an output section.

[VincentWu]

Refactoring the implementation of lld from psABI.
rebase & address comments

[VincentWu]

lld/ELF/Arch/RISCV.cpp

899

Use R_RISCV_32 or R_RISCV_64 instead

lld/ELF/Writer.cpp

1652

IMHO, we can calculate the gain value directly if we scan them when all relaxation have been done.

[VincentWu]

Reduce the time complexity of the algorithm by storing symbol pointers instead of symbol names

Try to compile *Vim* with zcmt opt, the code size of result is about 2.5M. get 0.1M (3.8%) code size decrease when it compare to the code size of *Vim* without zcmt (2.6M).

[VincentWu]

extend the size of InputSection

[MaskRay]

In D134600#4289590, @VincentWu wrote:

extend the size of InputSection

Why is this change? InputSection may have millions of instances for a large link. Increasing a word may increase the peak memory usage by 1%. We should strive to avoid it.

[VincentWu]

Revert commit "extend sizeof InputSection"

[jrtc27]

lld/ELF/Arch/RISCV.cpp

338

These are extremely dodgy

762

Blank line doesn't match style

766

This naming doesn't fit

1184

"Entrys" is not an English word

1217

We call finalizeContents more than once?

lld/ELF/SyntheticSections.cpp

42 ↗

(On Diff #516290)

?

[kito-cheng]

lld/ELF/Arch/RISCV.cpp

338

See https://github.com/llvm/llvm-project/blob/main/lld/ELF/Arch/RISCV.cpp#L53-L54 , I think we can use same way here.

[VincentWu]

address comments

[VincentWu]

lld/ELF/Arch/RISCV.cpp

1217

This method will be called at the end of the last round of relaxation. the changed in Writer<ELFT>::finalizeAddressDependentContent() might be set as true, which will cause the linker to do an additional relaxation. the code here is just try to avoiding it being called again in an additional relaxation.

[jrtc27]

lld/ELF/Arch/RISCV.cpp

338

Uh, what is this diff now? That's not what Kito said to do, and doesn't make it less dodgy. All you've done is given it a name, but that doesn't change the fact that the whole approach is dodgy.

[VincentWu]

use INTERNAL_ relocation type for Zcmt