This is an archive of the discontinued LLVM Phabricator instance.

[JITLink][RISCV] Implement linker relaxation
ClosedPublic

Authored by jobnoorman on Apr 29 2023, 12:12 PM.

Details

Summary

This patch is essentially an adaption of LLD's algorithm to JITLink.
Currently, only relaxing R_RISCV_CALL(_PLT) and R_RISCV_ALIGN is
implemented, other relocations can follow later.

From a high level, the algorithm works as follows. In the first phase
(relaxBlock), we iteratively try to relax all instructions that have a
R_RISCV_RELAX relocation:

  • If, based on the current symbol values, an instruction sequence can be relaxed (i.e., replaced by a shorter instruction), we record how many bytes would be removed, the new instruction (Writes), and the new relocation type (EdgeKinds).
  • We keep track of the total number of bytes that got removed up to each relocation in the RelocDeltas array. This is the cumulative sum of the number of bytes removed for each relocation.
  • Symbol values and sizes are updated based on the number of removed bytes.
  • If for any relocation, the current RelocDeltas value doesn't match the one from the previous iteration, something changed and we need to run another iteration as some symbols might now have different values.

In the second phase (finalizeBlockRelax), all code is moved based on
RelocDeltas, the relaxed instructions are rewritten using Writes, and
R_RISCV_ALIGN is handled (moving instructions to ensure alignment and
inserting the correct NOP-sequence if needed). Finally, edge kinds and
offsets are updated and all R_RISCV_RELAX and R_RISCV_ALIGN edges are
removed (they are not needed anymore for the fixup linking stage).

Linker relaxation is implemented as a pass and added to PreFixupPasses
in the default configuration on RISC-V.

Since linker relaxation removes instructions, the memory for blocks
should ideally be reallocated. However, I believe this is currently not
possible in JITLink. Therefore, relaxation directly modifies the memory
of blocks, reducing the number of instructions but not the size of
blocks. I'm not very familiar with JITLink's memory allocators so I
might be overlooking something here, though.

Note on testing: some of the tests rely on the debug output of
llvm-jitlink. The main reason for this is the verification of symbol
sizes (which may change due to relaxation). I don't believe this can be
done using jitlink-check checks alone.

Note that there is a slightly unrelated change that makes
Symbol::setOffset public to be able to update symbol offsets during
relaxation. I felt this change didn't warrant a separate patch but I can
split it off if necessary.

@MaskRay: I've added you as a reviewer since you're the original author
of the LLD algorithm. The algorithm in this patch is mostly the same as
yours but I made some minor modifications. The main one is that I got
rid of the valueDelta map you use in relax() to keep track of of the
deltas of symbols in the previous iteration in order to correctly update
symbol values. I believe this is unnecessary and the same can be
accomplished by using the original symbol value stored in offset field
in its anchor. When making the same change in LLD, all tests still pass.

Depends on D149522 and D149523 and D149525 and D149541

Diff Detail

Event Timeline

jobnoorman created this revision.Apr 29 2023, 12:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 29 2023, 12:12 PM
jobnoorman requested review of this revision.Apr 29 2023, 12:12 PM
jobnoorman edited the summary of this revision. (Show Details)

Rebase on new dependency.

It took me a moment to find where the new code is actually used.

You go a bit to far with the anonymous namespace:
https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

Hahnfeld added inline comments.
llvm/include/llvm/ExecutionEngine/JITLink/riscv.h
205–211

Please keep this sorted based on the enum values (see comment at the top)

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp
523

Should this error more gracefully than asserting, also in Release builds?

589–592

I'm probably missing something here: Why is this only possible in RV32?

823–826

same here, please keep this sorted

llvm/lib/ExecutionEngine/JITLink/riscv.cpp
81–84

same

jrtc27 added inline comments.Apr 30 2023, 1:11 PM
llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp
589–592

C.JAL’s encoding means something else for RV64 (I think C.ADDIW but don’t remember for sure)

jobnoorman updated this revision to Diff 518656.May 2 2023, 2:18 AM

Only use anonymous namespace for classes, make functions static.

jobnoorman added inline comments.May 2 2023, 2:22 AM
llvm/include/llvm/ExecutionEngine/JITLink/riscv.h
205–211

These edge kinds will be removed in the next version of this patch.

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp
523

It should indeed.

I'm going to make a small modification to the implementation based on a comment in another review:

For R_RISCV_RELAX we should add relaxable edge kinds to the RISCV edge kinds enum (along the same lines as the x86-64 relaxable edges, and we should take this opportunity to rename the RISCV edges to bring them in line with the other architectures). When the ELF/RISCV LinkGraphBuilder sees an R_RISCV_RELAX relocation it should choose the relaxable variant for the corresponding edge.

This will also move the detection of this kind of error to a different location so I will implement your suggestion there.

jobnoorman updated this revision to Diff 518680.May 2 2023, 4:38 AM

Implement the following suggestion:

For R_RISCV_RELAX we should add relaxable edge kinds to the RISCV edge kinds enum (along the same lines as the x86-64 relaxable edges, and we should take this opportunity to rename the RISCV edges to bring them in line with the other architectures). When the ELF/RISCV LinkGraphBuilder sees an R_RISCV_RELAX relocation it should choose the relaxable variant for the corresponding edge.

The new edge kinds are called CallRelaxable and AlignRelaxable.

Note that I think we should do the renaming of other edges in a different patch.

@MaskRay: I've added you as a reviewer since you're the original author of the LLD algorithm. The algorithm in this patch is mostly the same as yours but I made some minor modifications. The main one is that I got rid of the valueDelta map you use in relax() to keep track of of the deltas of symbols in the previous iteration in order to correctly update symbol values. I believe this is unnecessary and the same can be accomplished by using the original symbol value stored in offset field in its anchor. When making the same change in LLD, all tests still pass.

See 6b1d151fe3dc530195d8802f1ecc247c8235dd3a for lld/ELF/Arch/RISCV.cpp:valueDelta.
lld/test/ELF/riscv-relax-call-intra-sec.s (use ninja check-lld-elf) will fail if you reset a symbol value to the original value.

@MaskRay: I've added you as a reviewer since you're the original author of the LLD algorithm. The algorithm in this patch is mostly the same as yours but I made some minor modifications. The main one is that I got rid of the valueDelta map you use in relax() to keep track of of the deltas of symbols in the previous iteration in order to correctly update symbol values. I believe this is unnecessary and the same can be accomplished by using the original symbol value stored in offset field in its anchor. When making the same change in LLD, all tests still pass.

See 6b1d151fe3dc530195d8802f1ecc247c8235dd3a for lld/ELF/Arch/RISCV.cpp:valueDelta.
lld/test/ELF/riscv-relax-call-intra-sec.s (use ninja check-lld-elf) will fail if you reset a symbol value to the original value.

I don't reset symbol values to their original but I use the original value to simply the calculation. I've opened D149735 to try to explain this a bit better :)

@MaskRay: I've added you as a reviewer since you're the original author of the LLD algorithm. The algorithm in this patch is mostly the same as yours but I made some minor modifications. The main one is that I got rid of the valueDelta map you use in relax() to keep track of of the deltas of symbols in the previous iteration in order to correctly update symbol values. I believe this is unnecessary and the same can be accomplished by using the original symbol value stored in offset field in its anchor. When making the same change in LLD, all tests still pass.

See 6b1d151fe3dc530195d8802f1ecc247c8235dd3a for lld/ELF/Arch/RISCV.cpp:valueDelta.
lld/test/ELF/riscv-relax-call-intra-sec.s (use ninja check-lld-elf) will fail if you reset a symbol value to the original value.

I don't reset symbol values to their original but I use the original value to simply the calculation. I've opened D149735 to try to explain this a bit better :)

Thanks. I think D149735 is good.

lhames accepted this revision.May 8 2023, 9:47 PM

I believe that this is blocked by the subtarget features patch, but otherwise LGTM.

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h
645–648

This could be moved to just below Symbol::getOffset to improve readability.

All defined symbols have blocks, so you could change the assert to:

assert(NewOffset < getBlock().getSize() && "Offset out of range");

to get a stricter bounds check.

This revision is now accepted and ready to land.May 8 2023, 9:47 PM
  • Move setOffset() to a better location;
  • Add stricter bounds check in setOffset().
jobnoorman marked an inline comment as done.May 8 2023, 11:29 PM

I believe that this is blocked by the subtarget features patch, but otherwise LGTM.

Thanks for the review @lhames!

Note that besides that patch, this is also still blocked by D149523 (for testing).

Rebase on update of D149522.

This revision was automatically updated to reflect the committed changes.

Hi @jobnoorman, unfortunately this doesn't seem to work for me in practice with the whole machinery of LLJIT, launching even the most basic program via lli -mattr=+relax:

define i32 @main() {
  ret i32 0
}

results in:

JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.run_atexits_helper" at address 0x2ae0d3969e is out of range of R_RISCV_CALL_PLT fixup at 0x3f8e8ac018 (__lljit_run_atexits, 0x3f8e8ac000 + 0x18)
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.run_atexits_helper" at address 0x2ae0d3969e is out of range of R_RISCV_CALL_PLT fixup at 0x3f8e8ac018 (__lljit_run_atexits, 0x3f8e8ac000 + 0x18)
./install/bin/lli: Failed to materialize symbols: { (<Platform>, { __dso_handle, atexit, __lljit_run_atexits }) }
Failed to materialize symbols: { (main, { __dso_handle, atexit, __lljit_run_atexits }) }

Could this have to do with copying the buffer? Could you take a look?

evandro removed a subscriber: evandro.May 17 2023, 3:44 PM

Thanks for reporting this, @Hahnfeld. Was this working before? I don't seem to be able to run your test file even without relaxation enabled. I'm getting slightly different errors though:

$ lli -jit-linker=jitlink test.ll
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008266008 (__lljit_run_atexits, 0x4008266000 + 0x8)
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008268008 (__lljit_run_atexits, 0x4008268000 + 0x8)
./lli: Failed to materialize symbols: { (<Platform>, { __lljit_run_atexits, atexit, __dso_handle }) }
Failed to materialize symbols: { (main, { __lljit_run_atexits, atexit, __dso_handle }) }

@Hahnfeld: the issue seems to be that by default, non-PIC code is generated. Adding --relocation-model=pic to the lli command line solves the issue for me.

Thanks for reporting this, @Hahnfeld. Was this working before?

Yes, it was working before, and still is working for me without -mattr=+relax.

$ lli -jit-linker=jitlink test.ll
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008266008 (__lljit_run_atexits, 0x4008266000 + 0x8)
JIT session error: In graph __standard_lib-jitted-objectbuffer, section .text: relocation target "__lljit.platform_support_instance" at address 0x40054e0cd0 is out of range of R_RISCV_HI20 fixup at 0x4008268008 (__lljit_run_atexits, 0x4008268000 + 0x8)
./lli: Failed to materialize symbols: { (<Platform>, { __lljit_run_atexits, atexit, __dso_handle }) }
Failed to materialize symbols: { (main, { __lljit_run_atexits, atexit, __dso_handle }) }

@Hahnfeld: the issue seems to be that by default, non-PIC code is generated. Adding --relocation-model=pic to the lli command line solves the issue for me.

This is because you're explicitly specifying -jit-linker=jitlink, then it doesn't default to PIC. If you don't specify anything, you'll still get JITLink (there is nothing else for RISC-V) and PIC by default. Then the test case works without linker relaxation, but you should see the error I posted above with -mattr=+relax.

Thanks for the explanation! I'll look into this more tomorrow but I just wanted to mention now that it does work for me, with and without relaxation.

I managed to reproduce this on qemu-system (was using qemu-user before and the addresses just happened to be close enough together to fit R_RISCV_CALL_PLT there).

Should be fixed by D150957.

Thanks again for reporting this @Hahnfeld!