[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 ↗

(On Diff #105400)

You can use llvm::remove_if.

1017 ↗

(On Diff #105400)

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

64 ↗

(On Diff #105611)

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.

66 ↗

(On Diff #105611)

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

ELF/Relocations.cpp

1012 ↗

(On Diff #105611)

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

64 ↗

(On Diff #105611)

I've added to the comment.

66 ↗

(On Diff #105611)

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

1012 ↗

(On Diff #105611)

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

64 ↗

(On Diff #106009)

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 ↗

(On Diff #106009)

Is this the same as Thunks.empty()?

1072–1074 ↗

(On Diff #106009)

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 ↗

(On Diff #106009)

Unnecessary style change.

ELF/Target.h

75 ↗

(On Diff #106009)

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 ↗

(On Diff #106009)

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.

1072–1074 ↗

(On Diff #106009)

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 ↗

(On Diff #106009)

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

ELF/Target.h

75 ↗

(On Diff #106009)

Done

[peter.smith]

Updated diff to address review comments.

[ikudrin]

ELF/Relocations.cpp

1087 ↗

(On Diff #106206)

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

1087 ↗

(On Diff #106206)

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

1087 ↗

(On Diff #106206)

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 ↗

(On Diff #108614)

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

987 ↗

(On Diff #111627)

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 ↗

(On Diff #111638)

nit: add blank lines before comments.

ELF/Relocations.h

138–148 ↗

(On Diff #111638)

Can you add blank lines between multi-line declarations?

165–166 ↗

(On Diff #111638)

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 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

Grammar nit: If a branch cannot reach.

73 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

Nit: period at end of comment.

77 ↗

(On Diff #114002)

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

78 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

Grammar nit: within range of a branch

80 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

Nit: period at the end of comment.

82 ↗

(On Diff #114002)

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

ELF/Relocations.cpp

981 ↗

(On Diff #114002)

Nit: period at the end of the comment.

1021 ↗

(On Diff #114002)

Period nit.

1027 ↗

(On Diff #114002)

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

1062 ↗

(On Diff #114002)

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

1066–1069 ↗

(On Diff #114002)

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

1074 ↗

(On Diff #114002)

Could ISR be made a const pointer?

1077 ↗

(On Diff #114002)

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.)

1078 ↗

(On Diff #114002)

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

1086 ↗

(On Diff #114002)

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 :)

1096–1097 ↗

(On Diff #114002)

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

1103 ↗

(On Diff #114002)

Could this parameter be made a const pointer?

1135 ↗

(On Diff #114002)

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

[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 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

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 ↗

(On Diff #114002)

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

1066–1069 ↗

(On Diff #114002)

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

1086 ↗

(On Diff #114002)

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.

1103 ↗

(On Diff #114002)

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.

ELF/Relocations.h

165–166 ↗

(On Diff #111638)

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

1090–1091 ↗

(On Diff #114182)

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.

1086 ↗

(On Diff #114002)

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.

1103 ↗

(On Diff #114002)

You're right; I'd missed that.

[smeenai]

ELF/Relocations.cpp

1086 ↗

(On Diff #114002)

• 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

1080 ↗

(On Diff #114370)

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

1080 ↗

(On Diff #114370)

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–166 ↗

(On Diff #111638)

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

91–92 ↗

(On Diff #118761)

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

lld/trunk/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;
+
+  // The placing of pre-created ThunkSections is controlled by the
+  // ThunkSectionSpacing parameter. The aim is to place the
+  // ThunkSection such that all branches from the InputSections prior to the
+  // ThunkSection can reach a Thunk placed at the end of the ThunkSection.
+  // Graphically:
+  // | up to ThunkSectionSpacing .text input sections |
+  // | ThunkSection                                   |
+  // | up to ThunkSectionSpacing .text input sections |
+  // | ThunkSection                                   |
+
+  // Pre-created ThunkSections are spaced roughly 16MiB 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 a branch cannot reach a pre-created ThunkSection a new one will be
+  // created so we can handle the rare cases of a Thumb 2 conditional branch.
+  // We intentionally use a lower size for ThunkSectionSpacing than the maximum
+  // branch range so the end of the ThunkSection is more likely to be within
+  // range of the branch instruction that is furthest away. The value we shorten
+  // ThunkSectionSpacing by is set conservatively to allow us to create 16,384
+  // 12 byte Thunks at any offset in a ThunkSection without risk of a branch to
+  // one of the Thunks going out of range.
+
+  // FIXME: lld assumes that the Thumb BL and BLX encoding permits the J1 and
+  // J2 bits to be used to extend the branch range. On earlier Architectures
+  // such as ARMv4, ARMv5 and ARMv6 (except ARMv6T2) the range is +/- 4MiB. If
+  // support for the earlier encodings is added then when they are used the
+  // ThunkSectionSpacing will need lowering.
+  ThunkSectionSpacing = 0x1000000 - 0x30000;
 }
 
 uint32_t ARM::calcEFlags() const {
   // We don't currently use any features incompatible with EF_ARM_EABI_VER5,
   // but we don't have any firm guarantees of conformance. Linux AArch64
   // kernels (as of 2016) require an EABI version to be set.
   return EF_ARM_EABI_VER5;
 }

lld/trunk/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(ArrayRef<OutputSection *> OutputSections);
-  ThunkSection *getOSThunkSec(OutputSection *OS, InputSectionDescription *ISD);
+  ThunkSection *getISDThunkSec(OutputSection *OS, InputSectionDescription *ISD);
   ThunkSection *getISThunkSec(InputSection *IS);
 
+  void createInitialThunkSections(ArrayRef<OutputSection *> OutputSections);
+
   void forEachInputSectionDescription(
       ArrayRef<OutputSection *> OutputSections,
       std::function<void(OutputSection *, InputSectionDescription *)> Fn);
 
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, RelType Type);
+
   ThunkSection *addThunkSection(OutputSection *OS, InputSectionDescription *,
                                 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

lld/trunk/ELF/Relocations.cpp

 
 // Merge the ThunkSections created this pass into the InputSectionDescriptions.
 void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> OutputSections) {
   forEachInputSectionDescription(
       OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
         if (ISD->ThunkSections.empty())
           return;
 
-        // Order Thunks in ascending OutSecOff
+        // Remove any zero sized precreated Thunks.
+        llvm::erase_if(ISD->ThunkSections, [](const ThunkSection *TS) {
+          return TS->getSize() == 0;
+        });
+        // Order Thunks in ascending OutSecOff.
         std::stable_sort(ISD->ThunkSections.begin(), ISD->ThunkSections.end(),
                          [](const ThunkSection *A, const ThunkSection *B) {
                            return A->OutSecOff < B->OutSecOff;
                          });
 
         // Merge sorted vectors of Thunks and InputSections by OutSecOff
         std::vector<InputSection *> Tmp;
         Tmp.reserve(ISD->Sections.size() + ISD->ThunkSections.size());
forEachInputSectionDescription(
         std::merge(ISD->Sections.begin(), ISD->Sections.end(),
                    ISD->ThunkSections.begin(), ISD->ThunkSections.end(),
                    std::back_inserter(Tmp), MergeCmp);
         ISD->Sections = std::move(Tmp);
         ISD->ThunkSections.clear();
       });
 }
 
-static uint32_t findEndOfFirstNonExec(OutputSection &Cmd) {
-  for (BaseCommand *Base : Cmd.SectionCommands)
-    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(OutputSection *OS,
+ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *OS,
                                            InputSectionDescription *ISD) {
+  // FIXME: When range extension thunks are supported we will need to check
+  // that the ThunkSection is in range of the caller.
   if (!ISD->ThunkSections.empty())
     return ISD->ThunkSections.front();
 
-  uint32_t Off = findEndOfFirstNonExec(*OS);
-  return addThunkSection(OS, ISD, Off);
+  // 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");
 }
 
 // Add a Thunk that needs to be placed in a ThunkSection that immediately
 // precedes its Target.
 ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS) {
   ThunkSection *TS = ThunkedSections.lookup(IS);
   if (TS)
     return TS;
if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
         TS = addThunkSection(TOS, ISD, IS->OutSecOff);
         ThunkedSections[IS] = TS;
         break;
       }
     }
   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, a single
+// ThunkSection at the end of the range will do.
+void ThunkCreator::createInitialThunkSections(
+    ArrayRef<OutputSection *> OutputSections) {
+  forEachInputSectionDescription(
+      OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
+        if (ISD->Sections.empty())
+          return;
+        uint32_t ISLimit;
+        uint32_t PrevISLimit = ISD->Sections.front()->OutSecOff;
+        uint32_t ThunkUpperBound = PrevISLimit + Target->ThunkSectionSpacing;
+
+        for (const InputSection *IS : ISD->Sections) {
+          ISLimit = IS->OutSecOff + IS->getSize();
+          if (ISLimit > ThunkUpperBound) {
+            addThunkSection(OS, ISD, PrevISLimit);
+            ThunkUpperBound = PrevISLimit + Target->ThunkSectionSpacing;
+          }
+          PrevISLimit = ISLimit;
+        }
+        addThunkSection(OS, ISD, ISLimit);
+      });
+}
+
 ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
                                             InputSectionDescription *ISD,
                                             uint64_t Off) {
   auto *TS = make<ThunkSection>(OS, Off);
   ISD->ThunkSections.push_back(TS);
   return TS;
 }
 

 // each InputSection. It must be called before the static symbol table is
 // finalized. If any Thunks are added to an InputSectionDescription the
 // offsets within the OutputSection 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<OutputSection *> OutputSections) {
   bool AddressesChanged = false;
+  if (Pass == 0 && Target->ThunkSectionSpacing)
+    createInitialThunkSections(OutputSections);
+
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into InputSectionDescriptions.
   // We separate the creation of ThunkSections from the insertion of the
   // ThunkSections as ThunkSections are not always inserted into the same
   // InputSectionDescription as the caller.
   forEachInputSectionDescription(
       OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
         for (InputSection *IS : ISD->Sections)
           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) {
               AddressesChanged = true;
               // Find or create a ThunkSection for the new Thunk
               ThunkSection *TS;
               if (auto *TIS = T->getTargetInputSection())
                 TS = getISThunkSec(TIS);
               else
-                TS = getOSThunkSec(OS, ISD);
+                TS = getISDThunkSec(OS, ISD);
               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);
           }
       });

lld/trunk/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;

lld/trunk/ELF/Target.h

public:
   unsigned DefaultMaxPageSize = 4096;
 
   uint64_t getImageBase();
 
   // 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;
+
   RelType CopyRel;
   RelType GotRel;
   RelType PltRel;
   RelType RelativeRel;
   RelType IRelativeRel;
   RelType TlsDescRel;
   RelType TlsGotRel;
   RelType TlsModuleIndexRel;

lld/trunk/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)