Embedding R_RISCV_RELAX to another relocations

[rui314]

Object files for RISC-V contain lots of R_RISCV_RELAX relocations, and the number seems astonishing. If my calculation is correct, if I build the mold linker as a release binary for RISC-V, R_RISCV_RELAX relocation records occupy more than 10% of the total input object files (the input object files are in total 132MiB, and they contains 615,542 R_RISCV_RELAX relocations, so the relocations occupy 615,542 * 24 = 14,773,008 bytes.) That's way more than what I expected.

(Can someone verify it with your binary? I believe my calculation is correct but still can't completely believe it because it's too big.)

We do care about object file size. Large object files don't only take up more disk space but also slows down build system because of slow IO.

R_RISCV_RELAX essentially conveys a single bit information that the relocation pointing to the same place is relaxable. But on disk, each R_RISCV_RELAX occupies 24 bytes of space on RV64 because it's represented as an independent relocation record. That's 192x data bloat. It feels we should do something to improve the situation. Do you all have any ideas on how to improve it?

As a starter, I'd like to propose the following scheme to embed the R_RISCV_RELAX bit to relocation record.

Proposal

RV64's relocation record looks like this:

struct {
  u64 r_offset;
  u32 r_type;
  u32 r_sym;
  i64 r_addend;
};

where r_type represents the relocation type. The maximum relocation type is currently limited to 256, and with all possible future extensions, it is hard to imagine that we'd need more than 2^16 distinctive relocation types (I believe we'll never have more than 1024 relocation types, but I'm erring on the side of caution.) That gives us the opportunity to redefine the upper half of the r_type record as follows:

struct {
  u64 r_offset;
  u16 r_type;
  u16 reserved : 15;
  u16 relaxable : 1;
  u32 r_sym;
  i64 r_addend;
};

relaxable bit is turned on if a relocation is relaxable. In this scheme, we can embed all R_RISCV_RELAX relocations to adjacent relocations.

If an object file containing the new relocation records is consumed by a tool that doesn't understand the new format, the tool would report an "unknown relocation type" error because the relaxable bit would be interpreted as part of r_type. So we need to implement it first to the linker and other ELF-consuming tools, wait for a few years and then turn it on for the assembler/compiler.

There are a few precedences to use the r_type records in a way similar to this. For example, SPARC stores a 24 bit immediate value in the most significant 24 bits of r_type if the relocation type is R_SPARC_OLO10. MIPS allows a single relocation records to contain up to 3 relocation types. In binutils, such relocations are first preprocessed and represented as two or three relocation records internally.

So, what do you think about this?

[jrtc27]

Well for starters that doesn't work for RV32 and we don't want gratuitous ABI divergence between the two, which this would be.

[rui314]

We can define a relocation with the "relaxable" bit as equivalent to a pair of the original relocation and a R_RISCV_RELAX pointing to the same location. In other words, the "relaxable" bit is just shorthand notation for two relocations and nothing more. BFD ld would actually handle it in that manner.

[MaskRay]

I think I have undergone a mindset shift regarding R_RISCV_RELAX. Initially, I'd use a fixed bit as well, provided we had the opportunity to redesign linker relaxation. The fact that ELFCLASS32 has a limit of 256 is not a significant issue. We can simply use composed relocations for niche types.

However, the idea of supporting the RVC/non-RVC difference (#393) makes me reconsider that R_RISCV_RELAX might not be as problematic as I initially thought. To minimize waste, we should consider reducing R_RISCV_RELAX for instructions that are used as a unit. Currently, some relaxable code sequences require each instruction to be paired with a R_RISCV_RELAX, which is inefficient.

[sorear]

We have to consider Zcmt and the Andes LWGP etc extension as well, possibly extensions that will affect relaxation of common symbol references.

[kito-cheng]

I inclined to the approach proposed by #393, which using ISA string to record the info, I think that could carry more information to resolve RVC/non-RVC issues.

[sorear]

If we wanted to go down this path, I think it would make more sense to define a shorthand relocation record and a new sh_type value for shorthand relocations (vaguely similar to the approach taken with DT_RELR) which would provide substantially less than 64 bits of offset and addend in addition to providing a 1-bit relaxation indicator. Any relocation record which does not fit in the offset/addend/type fields, or which requires more than 1 bit to indicate its relaxation properties, would need to use the full relocation record.

[MaskRay]

My CREL proposal will make .o size significantly smaller without embedding.
https://discourse.llvm.org/t/rfc-crel-a-compact-relocation-format-for-elf/77600

build	format	.o size	size(.rel*)	.o	size decrease
x86_64 -O3	RELA	136012504	28235448	
x86_64 -O3	CREL	111583312	3806234	18.0%
aarch64 -O3	RELA	124965808	25855800	
aarch64 -O3	CREL	102529784	3388307	18.0%
ppc64le -O3	RELA	129017272	26589192	
ppc64le -O3	CREL	105860576	3432419	17.9%
riscv64 -O3	RELA	227189744	91396344	
riscv64 -O3	CREL	149343352	13549699	34.3%

I started llvm-project patches for CREL. Relocatable file size isn't a major concern for a few folks on https://groups.google.com/g/generic-abi/c/yb0rjw56ORw