[ELF] Try placing newly created ThunkSection at the end of the InputSection first

[MaskRay]

Summary

Inspired by PR40740.

It increases the probability that the thunk section can be shared by a
subsequent InputSection, thus potentially decreases the total number of
thunk sections.

[MaskRay]

It is inspired by PR40740. It doesn't fix it.

The nice property would be extremely difficult to test directly after both PPC64/MIPS move towards getThunkSectionSpacing (I know little about MIPS to craft a MIPS test..). Just wanted to know if you think this is good to do before I start updating the following tests.

lld :: ELF/aarch64-cortex-a53-843419-large.s
lld :: ELF/arm-long-thunk-converge.s
lld :: ELF/arm-thumb-condbranch-thunk.s
lld :: ELF/arm-thumb-thunk-empty-pass.s
lld :: ELF/arm-thunk-re-add.s
lld :: ELF/ppc64-bsymbolic-toc-restore.s
lld :: ELF/ppc64-call-reach.s
lld :: ELF/ppc64-ifunc.s
lld :: ELF/ppc64-local-dynamic.s
lld :: ELF/ppc64-plt-stub.s
lld :: ELF/ppc64-toc-restore-recursive-call.s
lld :: ELF/ppc64-toc-restore.s

[ruiu]

Makes sense. LGTM

[peter.smith]

I don't think it will do any harm, but it is probably not going to make a lot of difference. The thunk code makes the assumption that there is one branch range for the thunk section spacing, the vast majority will get placed in these sections. The no suitable ThunkSection case is for the small number of edge cases that don't fit the model, for example in Thumb there is one very rare branch that has a much shorter range so it may need to use this, but there aren't enough of them to make reuse opportunities that likely.

[MaskRay]

In D61629#1493047, @peter.smith wrote:

I don't think it will do any harm, but it is probably not going to make a lot of difference. The thunk code makes the assumption that there is one branch range for the thunk section spacing, the vast majority will get placed in these sections. The no suitable ThunkSection case is for the small number of edge cases that don't fit the model, for example in Thumb there is one very rare branch that has a much shorter range so it may need to use this, but there aren't enough of them to make reuse opportunities that likely.

createInitialThunkSections() looks to me a very good global heuristic. Without it, Relocations.cpp:1669 getISDThunkSec is making local decisions that may not be very good. I think it this way. There are three positions to create the thunk:

• IS->OutSecOff: current status
• IS->OutSecOff + IS->getSize(): this patch. It improves sharing slightly.
• The last InputSection whose start address is before IS->OutputSecOff + getThunkSectionSpacing(). This is the best place to insert the thunk. (This is heuristically achieved by the proactive createInitialThunkSections().

If you think the marginal benefit is not bad to have, I'll update the tests:)

[peter.smith]

In D61629#1493114, @MaskRay wrote:

In D61629#1493047, @peter.smith wrote:

I don't think it will do any harm, but it is probably not going to make a lot of difference. The thunk code makes the assumption that there is one branch range for the thunk section spacing, the vast majority will get placed in these sections. The no suitable ThunkSection case is for the small number of edge cases that don't fit the model, for example in Thumb there is one very rare branch that has a much shorter range so it may need to use this, but there aren't enough of them to make reuse opportunities that likely.

createInitialThunkSections() looks to me a very good global heuristic. Without it, Relocations.cpp:1669 getISDThunkSec is making local decisions that may not be very good. I think it this way. There are three positions to create the thunk:

• IS->OutSecOff: current status
• IS->OutSecOff + IS->getSize(): this patch. It improves sharing slightly.
• The last InputSection whose start address is before IS->OutputSecOff + getThunkSectionSpacing(). This is the best place to insert the thunk. (This is heuristically achieved by the proactive createInitialThunkSections().

If you think the marginal benefit is not bad to have, I'll update the tests:)

I don't have any objections, just wanted to save you the work of updating the tests!

In an ideal world we would have something similar to IS->OutputSecOff + getThunkSectionSpacing() although it would need some modifications. For example the last case of IS->OutputSecOff + getThunkSectionSpacing() in its current form would not work for Thumb2. The getThunkSectionSpacing() uses a singler per architecture value, which is 16 Megabytes for Thumb2 representing the branch range of the unconditional branches, the (much rarer) conditional branch instruction has a range of 1 Megabyte. We would need a more sophisticated implementation that took into account the specific branch range of the type of the relocation when calculating the ThunkSectionSpacing.

[MaskRay]

I may revive it after the ppc64 tests are fixed by D61610 :)

ELF/Relocations.cpp

if (Target->inBranchRange(Type, Src, (Src > TSLimit) ? TSBase : TSLimit))
       return TS;
   }
 
   // No suitable ThunkSection exists. This can happen when there is a branch
   // with lower range than the ThunkSection spacing or when there are too
   // many Thunks. Create a new ThunkSection as close to the InputSection as
   // possible. Error if InputSection is so large we cannot place ThunkSection
   // anywhere in Range.
-  uint64_t ThunkSecOff = IS->OutSecOff;
+  uint64_t ThunkSecOff = IS->OutSecOff + IS->getSize();
   if (!Target->inBranchRange(Type, Src, OS->Addr + ThunkSecOff)) {
-    ThunkSecOff = IS->OutSecOff + IS->getSize();
+    ThunkSecOff = IS->OutSecOff;
     if (!Target->inBranchRange(Type, Src, OS->Addr + ThunkSecOff))
       fatal("InputSection too large for range extension thunk " +
             IS->getObjMsg(Src - (OS->Addr + IS->OutSecOff)));
   }
   return addThunkSection(OS, ISD, ThunkSecOff);
 }
 
 // Add a Thunk that needs to be placed in a ThunkSection that immediately