[llvm-dev] [LLVM-DEV][LLD] RFC Range Thunks Implementation review for ARM and Mips

[Peter Smith via llvm-dev]

This RFC is primarily to support the review of the range extension
thunks implementation of lld. This concerns ARM and Mips as all of the
thunk creation step is skipped over if the target doesn't need thunks.

Mips LA25 Thunks are not range extension Thunks but these are
generated using the same code, I've kept the behaviour the same as it
is now, although the implementation is obviously slightly different in
the detail.

Recap of range extension thunks
- Many architectures with fixed instruction width have a branch instruction
that has a limited range
- On ARM and AArch64 the static linker is expected to insert range extension
thunks when some classes of branch instruction are out of range

Where are we now with LLD and thunks
- We have moved the createThunks() function as late as it can be in
finalizeSections(), most importantly after all the content has been
added to the image.
- We only call createThunks() once and we don't calculate addresses
before createThunks().
- If an OutputSection is described by a LinkerScript then any thunks
created in it are put at the end of the OutputSection. This is due to
the LinkerScript not being aware of the thunks (InputSections) in the
InputSectionDescriptions.

Proposed implementation for range extension thunks
At a high-level we need to solve the following problems:
- Assign addresses more than once
- Maintain state between successive calls of createThunks()
- Synchronization of the linker script and the OutputSection after adding thunks
- Deciding when we need a range extension thunk and where to place it so that it
can be reused by multiple callers.

The first 3 problems are where range extension thunks interact most
with the rest of the linker. The last problem can be confined to the
thunk implementation.

Address Assignment
The non-linker script address assignment can already be called
multiple times. The linker script address assignment records state as
it goes, if this state is reset it can be called more than once.

Maintaining state between successive calls to createThunks()
I've chosen to introduce a class ThunkCreator that can maintain the
state between calls.

Synchronization of OutputSection and linker scripts
An OutputSection described by a linker script SECTIONS command has one
or more InputSectionDescriptions that control how InputSections are
laid out in that OutputSection. If a thunk section is added to
OutputSection.Sections it must be added to the correct
InputSectionDescription. For the implementation I have chosen to add
Thunks to OutputSection.Sections and then merge these into the
InputSectionDescriptions for the OutputSection.

Placement of range extension thunks
I have chosen a simple implementation of spacing ThunkSections a
Target dependent distance apart. For ARM (lld currently supports v7a)
this is set to the Thumb2 branch range of 16Mb. If a thunk cannot be
created in one of these spaced out ThunkSections a new ThunkSection is
created. This allows special cases such as the Thumb2 conditional
branch with a range of 1Mb to be supported without reducing the
spacing of the pool.

This is a different approach to ld.bfd and gold, in gold at least a
thunk (Stub) must be placed within one of the precreated
ThunkSections, these are called stub groups. There is a command line
option --stub-group-size that allows the user some kind of control
over the spacing. I've not implemented the command-line option in the
initial implementation.

Reviews:
I've created reviews for a series of patches that implement range
extension thunks, I expect that these will need quite a bit of work,
especially the first three. If you've got any comments on the code, or
anything local to the patch I'd be grateful if you could leave a
comment on the relevant review. If there is anything more general then
responding to this message may be better.

The majority of the actual work is writing the tests, which should be
resusable however the implementation ends up.

The following patches are the glue code needed for range extension thunks to
be implemented.
[LLD][ELF] Make createThunks a class [NFC]
https://reviews.llvm.org/D31654
[LLD][ELF] Fix Thunks with placement restrictions and linker scripts
https://reviews.llvm.org/D31656
[LLD][ELF] Make createThunks() iterate until no more thunks added
https://reviews.llvm.org/D31657

The following set of patches add range extension thunks, they are split up to
make reviewing easier, but don't add enough to add tests until late on.
[ELF] Introduce Thunk reuse compatibility
https://reviews.llvm.org/D31658
[ELF] Be more precise about Thumb state bit in ARM thunks
https://reviews.llvm.org/D31659
[ELF] Allow multiple thunks to be added for a symbol
https://reviews.llvm.org/D31660
[ELF] Pre-create ThunkSections at Target specific intervals
https://reviews.llvm.org/D31661
[ELF] Introduce range extension thunks for ARM
https://reviews.llvm.org/D31662
[ELF] Account for range thunk that has drifted out of range
https://reviews.llvm.org/D31663
[ELF] Prefer placing ThunkSections before non ThunkSections
https://reviews.llvm.org/D31664
[ELF] Add test cases for range extension thunks (no linkerscripts)
https://reviews.llvm.org/D31665
[ELF] Add test cases for range extension thunks using linkerscripts
https://reviews.llvm.org/D31666

Peter