[LLD][ELF] Pre-create ThunkSections at Target specific intervals

[peter.smith]

Summary

When an OutputSection is larger than the branch range for a Target we need to place thunks such that they are always in range of their caller, and sufficiently spaced to maximise the number of callers that can use the thunk. We use the simple heuristic of placing the ThunkSection at intervals corresponding to a target specific branch range. If the OutputSection is small we put the thunks at the end of the executable sections.

The overall design for range thunks is for each InputSectionDescription pre-create ThunkSections at regularly spaced intervals in which we can place range extension thunks that are within range of their caller. This is similar to the stub-groups implemented by bfd and clang.

This is patch 6/11 of range thunks. It is dependent on D34688 and its dependencies.

[peter.smith]

Rebased, no other changes.

[grimar]

ELF/Relocations.cpp

979

You can use llvm::remove_if.

1016

It is equal to next, right ?

if (!ThunkSections[ISR].empty())
  return ThunkSections[ISR].front();

[peter.smith]

Updated to incorporate George's comments. I've applied both suggestions.

[ruiu]

ELF/Arch/ARM.cpp

66

Can you extend the comment so that it is more friendly to those who don't know much about ARM? e.g. Thumb unconditional branch instructions have xx bit displacement, so it can jump to +-yy bytes. We insert thunks for at least yy bytes to support longer jumps.

68

Why do you want to limit the size of thunk size?

ELF/Relocations.cpp

1011–1025

What is ISR? Adding a function comment would help.

[peter.smith]

Thanks for the comments, I'll update the diff.

What I'm aiming for is:

Section 0.0
...
Precreated RangeThunk
; (dot) - Section 0.0->OutSecOff < ThunkSectionSpacing)
Section 1.0
...
Precreated RangeThunk
; (dot) - Section 1.0->OutSecOff < ThunkSectionSpacing)

This is a simple way of making sure that as many branches within the gaps between ThunkSections can reach their targets without needing additional ThunkSections creating on later passes.

ELF/Arch/ARM.cpp

66

I've added to the comment.

68

What I'm trying to achieve is something like:

Range of sections:
start:
Section 0 at OutSecOff 0
...
RangeThunk at offset OFF from start. Where (RangeThunk.OutSecOff + RangeThunk.Size) - start < ThunkSectionSpacing

The ThunkSectionSize is a pessimistic guess at the final RangeThunk.Size so that we can guarantee that a branch at offset 0 can reach anywhere within RangeThunk.

ELF/Relocations.cpp

1011–1025

I've added a comment. ISR is meant to stand for Input Section Range, which is supposed to represent a range of InputSections (specifically those that come from a single InputSectionDescription), I used range rather than description as at one point we had a distinction between the script and non-script cases.

I'm open to suggestions for better names, or I can expand them to make them a bit more self-descriptive?

[peter.smith]

Updated diffs to add additional comments. No change to code.

[ruiu]

ELF/Arch/ARM.cpp

66

By "b", I believe you actually meant "B" (i.e. not bit but byte). Probably the best way of representing it is 16 MiB.

ELF/Relocations.cpp

982

Is this the same as Thunks.empty()?

1070–1072

It seems IS is always a member of ISR, but it is not obvious why forEachExecInputSection is designed like that. Maybe we should change the type of the function from

forEachExecInputSection(ArrayRef<OutputSectionCommand *> OutputSections,
    std::function<void(OutputSection *, std::vector<InputSection *> *,
                       InputSection *)> Fn)

to

forEachExecInputSection(ArrayRef<OutputSectionCommand *> OutputSections,
    std::function<void(OutputSection *, std::vector<InputSection *> *)> Fn)

and run a for-loop inside the callback function.

1134–1135

Unnecessary style change.

ELF/Target.h

78

nit: just 0 as GotBaseSymOff is set to just 0.

[peter.smith]

Thanks very much for the review comments, I'll update the diff shortly.

ELF/Relocations.cpp

982

Not quite as remove_if won't reduce the size of the vector unless Thunks.erase is called. Given that I managed to forget to consistently use ThunkBegin and ThunkEnd after various review cycles makes me think it is best to call Thunks.erase(). I've made that update as it means that ThunkBegin and ThunkEnd can be removed.

1070–1072

I've made the change. The reason I originally had it in forEachExecInputSection() was to reduce the level of indentation needed in the callbacks.

1134–1135

I've run clang-format on the file, hopefully there aren't too many just white-space differences.

ELF/Target.h

78

Done

[peter.smith]

Updated diff to address review comments.

[ikudrin]

ELF/Relocations.cpp

1086

As now you create Thunk sections in advance, it is possible that they stay empty when ThunkCreator::mergeThunks() is called. In that case, it might call getTargetInputSection() on an empty ThunkSections, which, on its turn, calls front() on an empty vector Thunks.

[peter.smith]

Thanks for the comment, I've put a response inline and hope to update the diff later today.

ELF/Relocations.cpp

1086

I think that with the most recent update I've changed the bit of code in mergeThunks to erase ThunkSections with 0 Thunks. Having said that given that getTargetInputSection() is supposed to be able to return nullptr when there is no target I think it makes sense to return nullptr in ThunkSection::getTargetInputSection() if there are no Thunks.

I'll aim to update the diff later today.

[ikudrin]

ELF/Relocations.cpp

1086

Oh, you are right. I didn't notice the change. I was playing with a patch from D34634 which was a bit outdated.

Thank you for the work!

[peter.smith]

Updated diff to return nullptr from ThunkSection::getTargetInputSection() when there are no Thunks.

[ikudrin]

It is possible that a precreated thunk section stays empty in the first pass, but is used in the next pass. In that case, it isn't added into ISR in ThunkCreator::mergeThunks(). For example:

$ cat a.s
	.global _start, foo
.section .text.start,"ax",%progbits
_start:
	bl _start
.section .text.dummy1,"ax",%progbits
.space 0xfffffe
.section .text.foo,"ax",%progbits
foo:
	bl _start
$ llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi a.s -o a.o
$ ld.lld a.o -o a.out
$ objdump -d a.out
a.out:     file format elf32-littlearm


Disassembly of section .text:

00011000 <_start>:
   11000:	f7ff effe 	blx	11000 <_start>

00011004 <__Thumbv7ABSLongThunk__start>:
   11004:	f241 0c00 	movw	ip, #4096	; 0x1000
   11008:	f2c0 0c01 	movt	ip, #1
   1100c:	4760      	bx	ip
	...

01011002 <__Thumbv7ABSLongThunk__start>:
	...

0101100c <foo>:
 101100c:	f7ff fff9 	bl	1011002 <__Thumbv7ABSLongThunk__start>

By the way, this sample shows one additional issue: redundant thunks are not removed.

[peter.smith]

In D34689#811237, @ikudrin wrote:

It is possible that a precreated thunk section stays empty in the first pass, but is used in the next pass. In that case, it isn't added into ISR in ThunkCreator::mergeThunks(). For example:

$ cat a.s
	.global _start, foo
.section .text.start,"ax",%progbits
_start:
	bl _start
.section .text.dummy1,"ax",%progbits
.space 0xfffffe
.section .text.foo,"ax",%progbits
foo:
	bl _start
$ llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi a.s -o a.o
$ ld.lld a.o -o a.out
$ objdump -d a.out
a.out:     file format elf32-littlearm


Disassembly of section .text:

00011000 <_start>:
   11000:	f7ff effe 	blx	11000 <_start>

00011004 <__Thumbv7ABSLongThunk__start>:
   11004:	f241 0c00 	movw	ip, #4096	; 0x1000
   11008:	f2c0 0c01 	movt	ip, #1
   1100c:	4760      	bx	ip
	...

01011002 <__Thumbv7ABSLongThunk__start>:
	...

0101100c <foo>:
 101100c:	f7ff fff9 	bl	1011002 <__Thumbv7ABSLongThunk__start>

By the way, this sample shows one additional issue: redundant thunks are not removed.

I think you are correct, and I'll need to address the problem of ThunkSections empty on the first pass but not used. I think D34692 would be the better place to do so as this is where multiple places are introduced. Would it be possible to make the comment in D34692, or I can copy it across?

I deliberately didn't try and remove Thunks that are redundant, I'm expecting redundant thunks to only happen when there is a Thunk that has been knocked out of range of all of its callers and I think this will be rare enough to not warrant the extra complexity.

[peter.smith]

Rebased to account for r308056 and r308057. I have also accounted for Rafael's observation in createInitialThunkSections that the spacing should subtract Target->ThunkSectionSize. I'll account for Igor's comment in D34692

[peter.smith]

Rebased and run through clang-format to account for "r308297 - Apply clang-format. NFC.". No other changes to patch.

[peter.smith]

Is there anything more I can do to progress the last three range thunks patches? I think I have all the outstanding comments received so far covered.

• D34689 Pre-create ThunkSections at Target specific intervals (this one)
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks()

[smeenai]

For whatever it's worth, I've been using these patches internally on a pretty large codebase, and they've worked really well; I haven't noticed any issues. It sounds like @ikudrin has been using them as well.

[peter.smith]

Rebased to account for r309311 Merge OutputSectionCommand and OutputSection. No other changes.

[peter.smith]

General ping for the remaining range thunks patches. If there is anything that I can do to make these easier to review please let me know? D34692 contains a large comment that explains the overall design.

• D34689 Pre-create ThunkSections at Target specific intervals (this one)
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks()

[ikudrin]

I'd like to say that I'm quite happy with this set of patches. We use them for Arm32 target with relatively large executables, and they seem to work well. It'd be great if these patches are ported to the release branch as well.

[peter.smith]

General ping for the remaining range thunks patches. D34692 contains a large comment that explains the overall design.

• D34689 Pre-create ThunkSections at Target specific intervals (this one)
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks()

There is also D34513, which is an optimization requested in D34692.

[smeenai]

@peter.smith I believe you meant to link to D35413.

Also, seconding what @ikudrin said. These patches are pretty vital for my use case (linking large libraries and executables for arm), so I've had them cherry-picked locally for a while now. Peter has been kind enough to keep rebasing these regularly, so they haven't been much of a maintenance burden for others, but it would be really nice to get these merged.

[peter.smith]

Yes thank you; I seem to have developed a habit for transposing numbers when typing. I would obviously like to get this functionality in as well, and will be happy to make any requested changes or provide further explanation. In the meantime I'll keep rebasing them when they fail to merge.

[peter.smith]

General ping for the remaining range thunks patches. D34692 contains a large comment that explains the overall design.

• D34689 Pre-create ThunkSections at Target specific intervals (this one)
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks()

There is also D35413, which is an optimization requested in D34692.

[emaste]

ELF/Arch/ARM.cpp

66

One more change to MiB needed here?

[peter.smith]

Thanks for the comment, I've updated the diff with the change from Mb to Mib.

[grimar]

Just a minor nit I noticed.

ELF/Relocations.cpp

980

You can use llvm::erase_if which is equivalent to C.erase(remove_if(C, pred), C.end());

[peter.smith]

Thanks for pointing out llvm::erase_if, I've updated the diff to use it.

[emaste]

(Aside, for FreeBSD we are rather eager to have this support arrive in lld upstream and will from there backport it to the lld 5.0.0 in our src tree. As it stands we cannot link the full base system with lld because lldb has grown too large -- https://bugs.freebsd.org/215691)

[peter.smith]

General ping for the remaining range thunks patches. Is there anything more I can do to progress these?

D34692 contains a large comment that explains the overall design.

• D34689 Pre-create ThunkSections at Target specific intervals (this one)
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks()

There is also D35413, which is an optimization requested in D34692.

[peter.smith]

General ping for the remaining range thunks patches. If it helps at all I will be at a conference in the Bay area 25th to 28th September, but I could escape to talk these over in person if any of the maintainers happened to be within public transport range.

D34692 contains a large comment that explains the overall design.

• D34689 Pre-create ThunkSections at Target specific intervals (this one)
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks()

There is also D35413, which is an optimization requested in D34692.

[ruiu]

ELF/Arch/ARM.cpp

66

nit: add blank lines before comments.

ELF/Relocations.h

138–148

Can you add blank lines between multi-line declarations?

165–167

This map is essentially a map from an InputSectionDescription to its thunks, right? Does it make more sense to add std::vector<ThunkSection *> to InputSectionDescription?

[peter.smith]

Thanks very much for the review comments. I've updated the diff with the extra spaces. I personally would prefer to stick with the map, but I'm happy to change it.

[smeenai]

Sorry about all the nits, but I figured I'd try to get all the mechanical issues out of the way, at least :)

ELF/Arch/ARM.cpp

69–71

These are the ranges in both the forward and backward direction, right? As in e.g. a Thumb BLX can branch 16 MiB forward or backward? It would probably be helpful to make that explicit (basically an ASCII-friendly equivalent to ±).

72

Grammar nit: If a branch cannot reach.

73

Grammar nit: should either be "the rare case of a Thumb 2 conditional branch" or "the rare case of Thumb 2 conditional branches".

74–75

This is confusing me slightly. It says LLD is assuming support for ARMv6T2 and above, so that includes ARMv6T2, but then it says "if support is added for ARMv6T2", which contradicts the previous sentence. Is there a typo somewhere?

76

Nit: period at end of comment.

77

Is there a general preference for expressing such constants in hex? For me, 16 * 1024 * 1024 is much more obviously 16 MiB.

78

If I'm understanding this correctly, the indented layout is:

|-------------------------------------------------------|
| Section: ThunkSectionSpacing - ThunkSectionSize bytes |
|-------------------------------------------------------|
|          ThunkSection: ThunkSectionSize bytes         |
|-------------------------------------------------------|
| Section: ThunkSectionSpacing - ThunkSectionSize bytes |
|-------------------------------------------------------|
|          ThunkSection: ThunkSectionSize bytes         |
|-------------------------------------------------------|
|                          ...                          |

When I was reading this originally, I got confused because I thought the intended layout was instead:

|-------------------------------------------------------|
|          Section: ThunkSectionSpacing bytes           |
|-------------------------------------------------------|
|          ThunkSection: ThunkSectionSize bytes         |
|-------------------------------------------------------|
|          Section: ThunkSectionSpacing bytes           |
|-------------------------------------------------------|
|          ThunkSection: ThunkSectionSize bytes         |
|-------------------------------------------------------|
|                          ...                          |

In hindsight, the name ThunkSectionSpacing makes the intended layout pretty clear, but it took me a while to grasp that. Maybe an explicit comment to that effect or an ASCII diagram could help?

79

Grammar nit: within range of a branch

80

Is the second part of the sentence supposed to imply that the start of the Section will be immediately after the end of the previous ThunkSection? It's not really clear to me.

81

Nit: period at the end of comment.

82

Same here; 16384 * 12 would be clearer to me.

ELF/Relocations.cpp

976

Nit: period at the end of the comment.

1018

Period nit.

1024

There's a run-on sentence; it should probably be "by creating a new one in range; for now, it is unreachable."

1101

Could this parameter be made a const pointer?

1108

Grammar nit: For an InputSectionRange that is smaller than the range, a single ThunkSection at the end of the range will do.

1112–1115

Can't all of these be moved inside the lambda?

1120

Could ISR be made a const pointer?

1123

If I'm understanding this code correctly, this if will only be entered in the first iteration of the loop. If that's the case, it's probably cleaner to just pull the body out and place it above the loop? That should also allow you to get rid of PrevISR.

(If ISR can be empty, you'd also need to check for that, of course.)

1124

Isn't this assignment dead, given that you unconditionally assign Off on line 1084?

1132

What happens if e.g. you have a single IS in this ISR, and its Off >= Limit? If I'm understanding this code correctly, you'll create a thunk at the start of the IS (i.e. IS->OutSecOff), and you won't create one at the end (because NeedTrailingTS will get set to false), but isn't the one at the end also needed?

More generally, I'm not sure about:

• Why do we create a thunk section at the start of the first IS, whereas all other thunk sections are at the end of ISs?
• How do we handle ISs which require multiple thunk sections?

I feel like I'm missing something pretty obvious, but it doesn't hurt to ask :)

1134–1135

You can get rid of the braces on this if now.

1142–1143

Remove the check for ISR->back() == IS and move this after the loop?

[peter.smith]

Thanks very much for the review comments, especially those surrounding createInitialThunkSections(), I've made an attempt at applying the suggestions.

[peter.smith]

I've added some inline comments to show what I changed.

ELF/Arch/ARM.cpp

74–75

I've reworded the sentence a bit. I've done some work downstream to support the older architectures (needs D36823 before I can upstream) so I've got a bit more information on what changes are needed.

77

I don't know if there is a preferred style in lld. From looking around it seems to be mostly decimal and sometimes hex. I've not seen the form 16 * 1024 * 1024 in the lld codebase. I've left the constants as they are for now but I'll happily change them if the consensus is to express them in another way.

78

Thanks for the suggestions. I've moved a description of the two parameters to the top and I've put in a diagram.

ELF/Relocations.cpp

1101

I don't think so, the ISR is the key in the map which usually means it can be const, but in mergeThunks we insert the ThunkSections into ISR so it needs to be non-const at that point. Let me know if I've missed a way of doing it though.

1112–1115

Yes they can, I've rewritten the function to account for your suggestions. Thanks very much I think that this simplifies it a bit.

1132

If I've understood correctly, for Off to be >= Limit then IS->getSize() must be >= (ThunkSectionSpacing - ThunkSectionSize), i.e. a gigantic InputSection. These are difficult to handle, and in some cases impossible (if there is a branch in the middle of a Section so large it can't escape the Section). I've put an answer for the 2nd bullet.

Why do we create a thunk section at the start of the first IS, whereas all other thunk sections are at the end of ISs?

I don't have a good answer for that so I've made it consistent. Initially the code was written when there was simultaneously OutputSections->Sections and InputSectionDescriptions and I probably haven't been aggressive enough at refactoring the function.

How do we handle ISs which require multiple thunk sections?

At present (with the latest modifications) we'll create a ThunkSection after the InputSection. This will be out of range of branches in the earlier part of the InputSection, but in range of the later part. In later patches (D34691 and D34692) we check to see if a ThunkSection is in range, if it isn't we create a new one prior to the InputSection, this should be in range of branches of the earlier part of the InputSection. We can't do anything if the Section is so large that a branch towards the middle can't escape. This might happen with an LTO build of a very large program that isn't compiled with -ffunction-sections so the whole program ends up in a single .text section, but I think it would be rare.

ELF/Relocations.h

165–167

The reasons I had to keep the mapping local were:

• The mapping is only needed when generating Thunks and as most Targets don't need them I wanted to avoid modifying the shared data structures that are visible to the end of the link.
• When there are multiple passes we need to remember not just the Thunks we've added but the ones that we have just added in the latest pass (See D34692) we would either need a map or to add yet another vector to InputSectionDescription.

I'm happy to change it if you'd prefer to store the fields in InputSectionDescription and remove the maps.

[smeenai]

Since the branch range we're supporting in this patch is ±16 MiB, in theory the thunk sections could be spaced 32 MiB apart instead of 16, with input sections jumping either forward or backward to thunks, correct? I understand it's probably not worth the additional complexity to support that, and I'm not suggesting changing it; I just wanted to confirm my understanding :)

ELF/Relocations.cpp

1101

You're right; I'd missed that.

1132

Yup, I was thinking of the case where IS->getSize() >= ThunkSectionSpacing - ThunkSectionSize. It makes sense that we can't handle that case completely, and a comment stating that would probably be helpful.

1136–1137

As I understand, the design relies on ThunkSections being used by InputSections prior to them. In that case, don't we always need a final trailing ThunkSection, to service the InputSections at the end?

In other words, with the current code, I believe an example layout could end up being something like:

InputSection
ThunkSection
InputSection
InputSection
InputSection
ThunkSection
InputSection
InputSection

I'm wondering if you need a ThunkSection at the end too, to service the last two InputSections in my example.

[smeenai]

ELF/Relocations.cpp

1132

• Why do we create a thunk section at the start of the first IS, whereas all other thunk sections are at the end of ISs?

I think I just figured my own question out. Conceptually, if the end of the current InputSection is beyond Limit, you'll add a ThunkSection at the end of the previous InputSection. For the very first InputSection, there's no previous one, in which case treating the start of the first InputSection as the end of the non-existent previous InputSection makes sense. You probably wanna go back to that behavior, sorry.

Instead of storing the entire PrevIS, how about just having a variable that keeps track of the end address of the previous section? I think that'd make the intent more immediately obvious, and its initialization to ISR->front()->OutSecOff could have a brief comment explaining the special casing for the first InputSection.

[peter.smith]

Thanks very much for the comments. Yes you are correct that the ThunkSpacing could be increased to ~32Mb after the first one, however I thought I'd try and keep it simple for the first iteration.

I've incorporated your suggestions into createInitialThunkSections(), in summary:

• I've removed PrevISR and moved to storing the previous insertion point, this removes the need for the conditional expression.
• I've renamed Off, Limit in favour of ISLimit and ThunkUpperBound, I'm hoping that this makes the intent clearer.
• I've removed the NeedsTrailingTS as it doesn't hurt to just add the trailing InputSection anyway as we'll just remove it if it isn't used.

[smeenai]

ELF/Relocations.cpp

1123

Should this be > instead of >=? ISLimit is one past the ending address of the current IS, and ThunkUpperBound is the maximum starting address of the thunk, so in the case where ISLimit == ThunkUpperBound, the thunk should be placed immediately after that IS, which is what a > comparison would accomplish.

[peter.smith]

ELF/Relocations.cpp

1123

I think you are most likely correct. I've got to leave the office right now, will pick this back up on Monday. Thanks very much again for the comments.

[peter.smith]

Yes you are correct, A < is better than <= as the ThunkSectionSpacing already lowers the start of the ThunkSection to be within range. I've updated the diff with the change and to account for D37627

[ruiu]

ELF/Relocations.h

165–167

I think I prefer adding all these stuffs to InputSectionDescription because (1) InputSectionDescription should be the central place to describe an input section and (2) doing hash table lookups that often could be slow.

[smeenai]

Thanks for all the updates! I tested the updated set of patches against our internal builds, and everything is still looking good.

[peter.smith]

I think I prefer adding all these stuffs to InputSectionDescription because (1) InputSectionDescription should be the central place to describe an input section and (2) doing hash table lookups that often could be slow.

I've implemented just the change to use InputSectionDescription in a separate refactoring review D37743.

[peter.smith]

Updated diff to rebase on top of the refactoring done in D37743 no other changes made.

[emaste]

Very small nit noticed on another look: there are couple of instances of Mib that should be MiB

[peter.smith]

Thanks for pointing the typos in the comment out, I've uploaded a new patch to fix them.

At the moment I've got 5 remaining reviews in the RangeThunks series. It would be great if I could get some feedback on how to progress these towards either approval or rejection as they have been present in much the same form (modulo refactoring) for several Months now. I'm wondering if there is anything more that I could or should be doing beyond replying to comments. Many thanks to everyone for all the comments received so far and I do appreciate that it is difficult to review a large Target specific change. I'd like to make it any easier to review, but I need a bit more feedback on the blocking areas as I've probably been staring at this too long.

The outstanding reviews can be committed in sequence without regressing from the previous patch.

• D37743 Record created ThunkSections in InputSectionDescription (Refactoring only)
• D34689 Pre-create ThunkSections at Target specific intervals
• D34691 Introduce range extension thunks for ARM
• D34692 Add support for multiple passes to createThunks
• D35413 Add DefinedInThunk to SymbolBody to remove need for hash lookup (Refactoring only)

[peter.smith]

For what it is worth I've created https://git.linaro.org/people/peter.smith/range-thunks-arm.git/ that contains all the range-thunks patches. I'll keep this in synch with the reviews.

[peter.smith]

Rebase in light of recent refactoring. No other changes.

[peter.smith]

Rebase on top of recent refactoring, no other changes.

[ruiu]

ELF/Arch/ARM.cpp

92–93

It is not clear to me if you really need this variable. If we understand correctly, we initially assume that we have thunks of 0x30000 bytes for each 0x1000000 bytes. But they are just rough initial estimation and doesn't have to be accurate, right? I wonder if we just assume that the size of thunk is zero. Or, if you really need it, can you assume that we have thunks of size zero for each 0x1000000 minus 0x30000 bytes?

[peter.smith]

Strictly speaking we don't need the ThunkSectionSize variable. I think it is worth having ThunkSectionSpacing less than the maximum branch range as it makes it more likely that all the thunks can be created in one pass. Does the value we reduce ThunkSectionSpacing by need to be as large as 16,384 Thunks, most likely not. It is a very conservative upper bound. I can change it but it will mean updating some of the tests in later approved reviews so I'd prefer not to do it here.

What I have done is to merge ThunkSectionSize into ThunkSectionSpacing by including the ThunkSectionSize in ThunkSectionSpacing, I've updated the comment to try and explain it a bit better as well.

[ruiu]

LGTM

ELF/Arch/ARM.cpp

ARM::ARM() {
   GotEntrySize = 4;
   GotPltEntrySize = 4;
   PltEntrySize = 16;
   PltHeaderSize = 20;
   TrapInstr = 0xd4d4d4d4;
   // ARM uses Variant 1 TLS
   TcbSize = 8;
   NeedsThunks = true;
+  // Pre-created ThunkSections are spaced roughly 16Mb apart on ARM. This is to
+  // match the most common expected case of a Thumb 2 encoded BL, BLX or B.W
+  // ARM B, BL, BLX range 32MiB
+  // Thumb B.W, BL, BLX range 16MiB
+  // Thumb B<cc>.W range 1MiB
+  // If branch cannot reach a pre-created ThunkSection a new one will be created
+  // so we can handle the rare case of Thumb 2 conditional branch.
+  // FIXME: lld assumes a CPU with support for ARMv6T2 and above encodings.
+  // If support is added for ARMv6T2 then when in use this spacing should drop
+  // to 4MiB
+  ThunkSectionSpacing = 0x1000000;
+  // The pre-created ThunkSections are inserted such that the end of the
+  // precreated ThunkSection is almost certain to be within range a branch
+  // from the start of the Section, or immediately following the previous
+  // ThunkSection. Allow for 16384 12 byte Thunks per ThunkSectionSpacing
+  ThunkSectionSize = 0x30000;
 }
 
 RelExpr ARM::getRelExpr(uint32_t Type, const SymbolBody &S,
                         const uint8_t *Loc) const {
   switch (Type) {
   default:
     return R_ABS;
   case R_ARM_THM_JUMP11:
     return R_PC;
   case R_ARM_CALL:
   case R_ARM_JUMP24:
   case R_ARM_PC24:
   case R_ARM_PLT32:
   case R_ARM_PREL31:
   case R_ARM_THM_JUMP19:
   case R_ARM_THM_JUMP24:
   case R_ARM_THM_CALL:
     return R_PLT_PC;
   case R_ARM_GOTOFF32:
     // (S + A) - GOT_ORG

ELF/Relocations.h

public:
 
   // The number of completed passes of createThunks this permits us
   // to do one time initialization on Pass 0 and put a limit on the
   // number of times it can be called to prevent infinite loops.
   uint32_t Pass = 0;
 
 private:
   void mergeThunks();
-  ThunkSection *getOSThunkSec(OutputSectionCommand *Cmd,
-                              std::vector<InputSection *> *ISR);
+  ThunkSection *getISRThunkSec(std::vector<InputSection *> *ISR);
   ThunkSection *getISThunkSec(InputSection *IS, OutputSection *OS);
-  void forEachExecInputSection(
+  void
+  createInitialThunkSections(ArrayRef<OutputSectionCommand *> OutputSections);
+  void forEachExecInputSectionRange(
       ArrayRef<OutputSectionCommand *> OutputSections,
-      std::function<void(OutputSectionCommand *, std::vector<InputSection *> *,
-                         InputSection *)>
+      std::function<void(OutputSectionCommand *, std::vector<InputSection *> *)>
           Fn);
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, uint32_t Type);
   ThunkSection *addThunkSection(OutputSection *OS,
                                 std::vector<InputSection *> *, uint64_t Off);
   // Record all the available Thunks for a Symbol
   llvm::DenseMap<SymbolBody *, std::vector<Thunk *>> ThunkedSymbols;
 
   // Find a Thunk from the Thunks symbol definition, we can use this to find
   // the Thunk from a relocation to the Thunks symbol definition.
   llvm::DenseMap<SymbolBody *, Thunk *> Thunks;
 
   // Track InputSections that have an inline ThunkSection placed in front
   // an inline ThunkSection may have control fall through to the section below
   // so we need to make sure that there is only one of them.
   // The Mips LA25 Thunk is an example of an inline ThunkSection.
   llvm::DenseMap<InputSection *, ThunkSection *> ThunkedSections;
 
   // All the ThunkSections that we have created, organised by OutputSection
   // will contain a mix of ThunkSections that have been created this pass, and
   // ThunkSections that have been merged into the OutputSection on previous
   // passes
   std::map<std::vector<InputSection *> *, std::vector<ThunkSection *>>
       ThunkSections;
-
-  // The ThunkSection for this vector of InputSections
-  ThunkSection *CurTS;
 };
 
 // Return a int64_t to make sure we get the sign extension out of the way as
 // early as possible.
 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rel &Rel) {
   return 0;
 }
 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/Relocations.cpp

 // in the Sections vector, and recalculate the InputSection output section
 // offsets.
 // This may invalidate any output section offsets stored outside of InputSection
 void ThunkCreator::mergeThunks() {
   for (auto &KV : ThunkSections) {
     std::vector<InputSection *> *ISR = KV.first;
     std::vector<ThunkSection *> &Thunks = KV.second;
 
+    // // Remove ThunkSections that contain no Thunks
+    Thunks.erase(
+        llvm::remove_if(
+            Thunks, [](const ThunkSection *TS) { return TS->getSize() == 0; }),
+        Thunks.end());
+    if (Thunks.empty())
+      continue;
+
     // Order Thunks in ascending OutSecOff
     auto ThunkCmp = [](const ThunkSection *A, const ThunkSection *B) {
       return A->OutSecOff < B->OutSecOff;
     };
     std::stable_sort(Thunks.begin(), Thunks.end(), ThunkCmp);
 
     // Merge sorted vectors of Thunks and InputSections by OutSecOff
     std::vector<InputSection *> Tmp;
auto MergeCmp = [](const InputSection *A, const InputSection *B) {
       return false;
     };
     std::merge(ISR->begin(), ISR->end(), Thunks.begin(), Thunks.end(),
                std::back_inserter(Tmp), MergeCmp);
     *ISR = std::move(Tmp);
   }
 }
 
-static uint32_t findEndOfFirstNonExec(OutputSectionCommand &Cmd) {
-  for (BaseCommand *Base : Cmd.Commands)
-    if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
-      for (auto *IS : ISD->Sections)
-        if ((IS->Flags & SHF_EXECINSTR) == 0)
-          return IS->OutSecOff + IS->getSize();
-  return 0;
-}
-
-ThunkSection *ThunkCreator::getOSThunkSec(OutputSectionCommand *Cmd,
-                                          std::vector<InputSection *> *ISR) {
-  if (CurTS == nullptr) {
-    uint32_t Off = findEndOfFirstNonExec(*Cmd);
-    CurTS = addThunkSection(Cmd->Sec, ISR, Off);
-  }
-  return CurTS;
+// Find or create a ThunkSection within the InputSectionRange (ISR) that is in
+// range of Src. An ISR maps to a range of InputSections described by a
+// linker script section pattern such as { .text .text.* }.
+// FIXME: At present we assume that all ThunkSections are in range so we always
+// return the first pre-created ThunkSection.
+ThunkSection *ThunkCreator::getISRThunkSec(std::vector<InputSection *> *ISR) {
+  // FIXME: When range extension thunks are supported we will need to check
+  // that the ThunkSection is in range of the caller
+  if (!ThunkSections[ISR].empty())
+    return ThunkSections[ISR].front();
+
+  // FIXME: When range extension thunks are supported we must handle the case
+  // where no pre-created ThunkSections are in range by creating a new one in
+  // range for now it is unreachable
+  llvm_unreachable("Must have created at least one ThunkSection per ISR");
 }
 
 ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS, OutputSection *OS) {
   ThunkSection *TS = ThunkedSections.lookup(IS);
   if (TS)
     return TS;
   auto *TOS = IS->getParent();
 
if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
         break;
       }
     }
   TS = addThunkSection(TOS, Range, IS->OutSecOff);
   ThunkedSections[IS] = TS;
   return TS;
 }
 
+// Create one or more ThunkSections per OS that can be used to place Thunks.
+// We attempt to place the ThunkSections using the following desirable
+// properties:
+// - Within range of the maximum number of callers
+// - Minimise the number of ThunkSections
+//
+// We follow a simple but conservative heuristic to place ThunkSections at
+// offsets that are multiples of a Target specific branch range.
+// For an InputSectionRange that is smaller than the range then a single
+// ThunkSection at the end of the range will do.
+void ThunkCreator::createInitialThunkSections(
+    ArrayRef<OutputSectionCommand *> OutputSections) {
+  bool NeedTrailingTS;
+  uint32_t Off;
+  uint32_t Limit;
+  InputSection *PrevIS = nullptr;
+  std::vector<InputSection *> *PrevISR = nullptr;
+
+  forEachExecInputSectionRange(
+      OutputSections,
+      [&](OutputSectionCommand *Cmd, std::vector<InputSection *> *ISR) {
+        for (InputSection *IS : *ISR) {
+          if (ISR != PrevISR) {
+            NeedTrailingTS = true;
+            Off = 0;
+            Limit = IS->OutSecOff +
+                    (Target->ThunkSectionSpacing - Target->ThunkSectionSize);
+            PrevIS = nullptr;
+            PrevISR = ISR;
+          }
+          Off = IS->OutSecOff + IS->getSize();
+          if (Off >= Limit) {
+            uint32_t ThunkOff = (PrevIS == nullptr)
+                                    ? IS->OutSecOff
+                                    : PrevIS->OutSecOff + PrevIS->getSize();
+            addThunkSection(Cmd->Sec, ISR, ThunkOff);
+            NeedTrailingTS = false;
+            Limit = ThunkOff + Target->ThunkSectionSpacing -
+                    Target->ThunkSectionSize;
+          }
+          PrevIS = IS;
+
+          if (ISR->back() == IS && NeedTrailingTS)
+            addThunkSection(Cmd->Sec, ISR, Off);
+        }
+      });
+}
+
 ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
                                             std::vector<InputSection *> *ISR,
                                             uint64_t Off) {
   auto *TS = make<ThunkSection>(OS, Off);
   ThunkSections[ISR].push_back(TS);
   return TS;
 }
 
 std::pair<Thunk *, bool> ThunkCreator::getThunk(SymbolBody &Body,
                                                 uint32_t Type) {
   auto Res = ThunkedSymbols.insert({&Body, std::vector<Thunk *>()});
   if (!Res.second) {
     // Check existing Thunks for Body to see if they can be reused
     for (Thunk *ET : Res.first->second)
       if (ET->isCompatibleWith(Type))
         return std::make_pair(ET, false);
   }
   // No existing compatible Thunk in range, create a new one
   Thunk *T = addThunk(Type, Body);
   Res.first->second.push_back(T);
   return std::make_pair(T, true);
 }
 
-// Call Fn on every executable InputSection accessed via the linker script
-// InputSectionDescription::Sections.
-void ThunkCreator::forEachExecInputSection(
+// Call Fn on every executable Range of InputSections accessed via the linker
+// script InputSectionDescription::Sections.
+void ThunkCreator::forEachExecInputSectionRange(
     ArrayRef<OutputSectionCommand *> OutputSections,
-    std::function<void(OutputSectionCommand *, std::vector<InputSection *> *,
-                       InputSection *)>
+    std::function<void(OutputSectionCommand *, std::vector<InputSection *> *)>
         Fn) {
   for (OutputSectionCommand *Cmd : OutputSections) {
     OutputSection *OS = Cmd->Sec;
     if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
       continue;
     for (BaseCommand *BC : Cmd->Commands)
       if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
-        CurTS = nullptr;
-        for (InputSection *IS : ISD->Sections)
-          Fn(Cmd, &ISD->Sections, IS);
+        Fn(Cmd, &ISD->Sections);
       }
   }
 }
 
 // Process all relocations from the InputSections that have been assigned
 // to OutputSections and redirect through Thunks if needed.
 //
 // createThunks must be called after scanRelocs has created the Relocations for
 // each InputSection. It must be called before the static symbol table is
 // finalized. If any Thunks are added to an OutputSection the output section
 // offsets of the InputSections will change.
 //
 // FIXME: All Thunks are assumed to be in range of the relocation. Range
 // extension Thunks are not yet supported.
 bool ThunkCreator::createThunks(
     ArrayRef<OutputSectionCommand *> OutputSections) {
   if (Pass > 0)
     ThunkSections.clear();
+  else if (Target->ThunkSectionSpacing)
+    createInitialThunkSections(OutputSections);
 
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into the OutputSection.
 
   // We separate the creation of ThunkSections from the insertion of the
   // ThunkSections back into the OutputSection as ThunkSections are not always
   // inserted into the same OutputSection as the caller.
-  forEachExecInputSection(OutputSections, [&](OutputSectionCommand *Cmd,
-                                              std::vector<InputSection *> *ISR,
-                                              InputSection *IS) {
+  forEachExecInputSectionRange(
+      OutputSections,
+      [&](OutputSectionCommand *Cmd, std::vector<InputSection *> *ISR) {
+        for (InputSection *IS : *ISR)
           for (Relocation &Rel : IS->Relocations) {
             SymbolBody &Body = *Rel.Sym;
             if (Thunks.find(&Body) != Thunks.end() ||
                 !Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body))
               continue;
             Thunk *T;
             bool IsNew;
             std::tie(T, IsNew) = getThunk(Body, Rel.Type);
             if (IsNew) {
               // Find or create a ThunkSection for the new Thunk
               ThunkSection *TS;
               if (auto *TIS = T->getTargetInputSection())
                 TS = getISThunkSec(TIS, Cmd->Sec);
               else
-          TS = getOSThunkSec(Cmd, ISR);
+                TS = getISRThunkSec(ISR);
               TS->addThunk(T);
               Thunks[T->ThunkSym] = T;
             }
             // Redirect relocation to Thunk, we never go via the PLT to a Thunk
             Rel.Sym = T->ThunkSym;
             Rel.Expr = fromPlt(Rel.Expr);
           }
       });
   // Merge all created synthetic ThunkSections back into OutputSection
   mergeThunks();
   ++Pass;
   return !ThunkSections.empty();
 }
 
 template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64BE>(InputSectionBase &);

ELF/SyntheticSections.cpp

 }
 
 void ThunkSection::writeTo(uint8_t *Buf) {
   for (const Thunk *T : Thunks)
     T->writeTo(Buf + T->Offset, *this);
 }
 
 InputSection *ThunkSection::getTargetInputSection() const {
+  if (Thunks.empty())
+    return nullptr;
   const Thunk *T = Thunks.front();
   return T->getTargetInputSection();
 }
 
 InputSection *InX::ARMAttributes;
 BssSection *InX::Bss;
 BssSection *InX::BssRelRo;
 BuildIdSection *InX::BuildId;

ELF/Target.h

public:
   // installs that is 65536, so the first 15 pages cannot be used.
   // Given that, the smallest value that can be used in here is 0x10000.
   uint64_t DefaultImageBase = 0x10000;
 
   // Offset of _GLOBAL_OFFSET_TABLE_ from base of .got section. Use -1 for
   // end of .got
   uint64_t GotBaseSymOff = 0;
 
+  // On systems with range extensions we place collections of Thunks at
+  // regular spacings that enable the majority of branches reach the Thunks.
+  uint32_t ThunkSectionSpacing = 0;
+
+  // An estimate of size of the Thunks that will be created per ThunkSection
+  uint32_t ThunkSectionSize = 0;
+
   uint32_t CopyRel;
   uint32_t GotRel;
   uint32_t PltRel;
   uint32_t RelativeRel;
   uint32_t IRelativeRel;
   uint32_t TlsDescRel;
   uint32_t TlsGotRel;
   uint32_t TlsModuleIndexRel;

test/ELF/arm-thumb-thunk-symbols.s

  .arm
  .balign 0x1000
  .globl arm_fn
  .type arm_fn, %function
 arm_fn:
  b thumb_fn
 
 // CHECK:     Name: __Thumbv7ABSLongThunk_arm_fn
-// CHECK-NEXT:     Value: 0x11005
+// CHECK-NEXT:     Value: 0x12005
 // CHECK-NEXT:     Size: 10
 // CHECK-NEXT:    Binding: Local (0x0)
 // CHECK-NEXT:    Type: Function (0x2)
 // CHECK:     Name: __ARMv7ABSLongThunk_thumb_fn
-// CHECK-NEXT:     Value: 0x11010
+// CHECK-NEXT:     Value: 0x12010
 // CHECK-NEXT:     Size: 12
 // CHECK-NEXT:    Binding: Local (0x0)
 // CHECK-NEXT:    Type: Function (0x2)
 
 // CHECK-PI:     Name: __ThumbV7PILongThunk_arm_fn
-// CHECK-PI-NEXT:     Value: 0x1005
+// CHECK-PI-NEXT:     Value: 0x2005
 // CHECK-PI-NEXT:     Size: 12
 // CHECK-PI-NEXT:    Binding: Local (0x0)
 // CHECK-PI-NEXT:    Type: Function (0x2)