[llvm-dev] RFC: LLD range extension thunks

[Peter Smith via llvm-dev]

The implementation will have to handle different branch ranges within
the same architecture, on ARM alone there are at least 3 ranges that
we'd have to handle within the same link [*].

At this stage I'd like to keep it simple and just handle the case of
redirecting a relocation to a target T to a thunk that will ultimately
transfer control to T.

I do have an interest in relaxation, primarily as a way to implement
errata patching, overwrite instruction with a branch to a patch thunk,
then return to a following instruction. However I think that is
something that can be built later as it is a generalisation of what we
would need for range extension thunks.

[*] A later revision of the ARM ELF document clarified that the linker
should not add Thunks for 16-bit Thumb branches, it is the
responsibility of the code-generator/author to only use these
instructions when the range to the target can be guaranteed. See Call
and Jump relocations on Page 33
http://infocenter.arm.com/help/topic/com.arm.doc.ihi0044f/IHI0044F_aaelf.pdf

On 19 January 2017 at 11:13, Bruce Hoult <bruce at hoult.org> wrote:
> Are you looking only at fixed length ISAs and adding thunks, or also at ISAs
> with different size branch instructions with different ranges, and relaxing
> short branches to either longer branches (if that will reach) or to thunks
> (if not)?
>
> Note that it's not purely "thunks for RISC" and "longer instructions for
> CISC". There are ISAs that could use a mixture of techniques.
>
> For example, Thumb2 has 16 bit branch instructions with a range of -252 -
> +256, and 32 bit branch instructions with a range of +/-16MB. If neither of
> those will work then you use a short or long branch to a thunk.
>
> Another example is RISC-V, which has:
>
> - 16 bit conditional branch instructions with +/-256 bytes range
> - 16 bit unconditional branch(&link) instructions with +/-2KB range
> - 32 bit conditional branch instructions with +/-2KB range
> - 32 bit unconditional branch(&link) instructions with +/-1MB range
> - 32 bit unconditional branch(&link) to reg +/-2KB offset that can be paired
> with a LUI or AUIPC (which load or add a 20 bit immediate shifted left by
> 12) to make a two instruction sequence that can do an absolute 32 bit branch
> or relative branch to PC +/ 2 GB.
>
> So thunks are never needed, but code size can change. If you're optimizing
> for size then it could be an advantage to use a thunk anyway, if it can be
> shared.
>
> The current clang & gcc versions always generate the full two instruction
> sequence, and then the linker deletes the LUI or AUIPC if the literal is
> zero. This does not produce as optimal code as starting with short branches
> and expanding the ones that won't reach.
>
> Both ARM and RISC-V ABIs have defined scratch registers that the linker (or
> other) can freely clobber for calculations inside thunks, or when converting
> instructions to multi-instruction sequences.
>
>
> On Thu, Jan 19, 2017 at 1:33 PM, Peter Smith via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> I think anything that we come up with will need to support Mips as
>> well as ARM and AArch64. I'm aware of the Mips LA25 Thunk and the need
>> for these Thunks to be placed before the Target Section. I'm intending
>> that the first patch that uses synthetic sections for Thunks will do
>> this. I'm not intending to go looking for new Mips Thunk types to
>> implement, I think it would be better that someone with more
>> experience of Mips and an ability to test properly, implemented these
>> [*]. I'm similarly ignorant of Power, which has limited range branch
>> instructions.
>>
>> My plan for implementation so far is to convert the existing
>> implementation to use synthetic sections without trying to do range
>> extension. When that is in and working we can build upon that to
>> include range extension. If we can make the range detection and thunk
>> placement sufficiently flexible it shouldn't be difficult to add new
>> Thunks later.
>>
>> [*] I can see that the pseudo-direct addressing used by J and JAL
>> instructions could in principle have range extension thunks and would
>> need different handling to ARM/AArch64 branches with PC-relative
>> offsets. I'm not sure whether Mips toolchains typically do use Thunks
>> in this case or if it is the caller's responsibility to use an
>> indirect jump via JR instead.
>>
>>
>> On 18 January 2017 at 23:59, Simon Atanasyan <simon at atanasyan.com> wrote:
>> >
>> >
>> > On Jan 19, 2017 2:48 AM, "Ed Maste" <emaste at freebsd.org> wrote:
>> >
>> > On 4 January 2017 at 13:34, Peter Smith via llvm-dev
>> > <llvm-dev at lists.llvm.org> wrote:
>> >> I'm about to start working on range extension thunks in lld. This is
>> >> an attempt to summarize the approach I'd like to take and what the
>> >> impact will be on lld outside of thunks.
>> >
>> > Now that LLD works well for FreeBSD/amd64 (and arm64 is very close)
>> > I'm looking at other architectures, starting with mips64. The
>> > statically-linked toolchain components currently fail to link with an
>> > out of range jump, so I'm very interested in seeing this work
>> > progress. Are you looking at only arm and AArch64? Once the
>> > infrastructure is in I'll try to take a look at mips if nobody else
>> > does first.
>> >
>> >
>> > I'm waiting for this changes too. Now mips thunks places at the end of
>> > the
>> > corresponding section. Not sure about FreeBSD but on Linux that leads to
>> > incorrect code in case of static linking -- a thunk goes between crt*.o
>> > files which needs to be "joined" together. Gnu linker puts thunks to the
>> > separate section. We need to do the same thing.
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>