ELF: Try to create last thunk section at ThunkSectionSpacing bytes before the end.

[pcc]

Summary

Now that we have the ability to create short thunks, it is beneficial
for thunk sections to be surrounded by ThunkSectionSpacing bytes
of code on both sides in order to increase the likelihood that the
distance from the thunk to the target will be sufficiently small to
allow for the creation of a short thunk. This is currently the case
for most thunks that we create, except for the last one, which could,
depending on the size of the output section, potentially appear near
the end and therefore have a relatively small amount of code after it.

This patch moves the last thunk section to ThunkSectionSpacing bytes
before the end of the output section, as long as the section is larger
than 2*ThunkSectionSpacing bytes. It reduces the size of Chromium
for Android's .text section by 32KB.

Depends on D44963

[peter.smith]

This sounds reasonable to me. For large programs there will be sufficient thunks that the small benefit to readability (all your thunks can be found at the end of the section) won't apply.

[ruiu]

LGTM

lld/trunk/ELF/Relocations.cpp

 // 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
+// For an InputSectionDescription that is smaller than the range, a single
 // ThunkSection at the end of the range will do.
+//
+// For an InputSectionDescription that is more than twice the size of the range,
+// we place the last ThunkSection at range bytes from the end of the
+// InputSectionDescription in order to increase the likelihood that the
+// distance from a thunk to its target will be sufficiently small to
+// allow for the creation of a short thunk.
 void ThunkCreator::createInitialThunkSections(
     ArrayRef<OutputSection *> OutputSections) {
   forEachInputSectionDescription(
       OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
         if (ISD->Sections.empty())
           return;
+        uint32_t ISDBegin = ISD->Sections.front()->OutSecOff;
+        uint32_t ISDEnd =
+            ISD->Sections.back()->OutSecOff + ISD->Sections.back()->getSize();
+        uint32_t LastThunkLowerBound = -1;
+        if (ISDEnd - ISDBegin > Target->ThunkSectionSpacing * 2)
+          LastThunkLowerBound = ISDEnd - Target->ThunkSectionSpacing;
+
         uint32_t ISLimit;
-        uint32_t PrevISLimit = ISD->Sections.front()->OutSecOff;
-        uint32_t ThunkUpperBound = PrevISLimit + Target->ThunkSectionSpacing;
+        uint32_t PrevISLimit = ISDBegin;
+        uint32_t ThunkUpperBound = ISDBegin + Target->ThunkSectionSpacing;
 
         for (const InputSection *IS : ISD->Sections) {
           ISLimit = IS->OutSecOff + IS->getSize();
           if (ISLimit > ThunkUpperBound) {
             addThunkSection(OS, ISD, PrevISLimit);
             ThunkUpperBound = PrevISLimit + Target->ThunkSectionSpacing;
           }
+          if (ISLimit > LastThunkLowerBound)
+            break;
           PrevISLimit = ISLimit;
         }
         addThunkSection(OS, ISD, ISLimit);
       });
 }
 
 ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
                                             InputSectionDescription *ISD,

lld/trunk/test/ELF/arm-thumb-mix-range-thunk-os.s

 // REQUIRES: arm
 // RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
 // RUN: ld.lld %t -o %t2 2>&1
 // The output file is large, most of it zeroes. We dissassemble only the
 // parts we need to speed up the test and avoid a large output file
 // RUN: llvm-objdump -d %t2 -start-address=1048576 -stop-address=1048604 -triple=armv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK1 %s
 // RUN: llvm-objdump -d %t2 -start-address=2097152 -stop-address=2097162 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK2 %s
 // RUN: llvm-objdump -d %t2 -start-address=16777220 -stop-address=16777232 -triple=armv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK3 %s
 // RUN: llvm-objdump -d %t2 -start-address=16777232 -stop-address=16777242 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK4 %s
 // RUN: llvm-objdump -d %t2 -start-address=32505860 -stop-address=32505870 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK5 %s
 // RUN: llvm-objdump -d %t2 -start-address=35651584 -stop-address=35651590 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK6 %s
 // RUN: llvm-objdump -d %t2 -start-address=36700160 -stop-address=36700168 -triple=armv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK7 %s
 // RUN: llvm-objdump -d %t2 -start-address=48234500 -stop-address=48234512 -triple=armv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK8 %s
-// RUN: llvm-objdump -d %t2 -start-address=63963140 -stop-address=63963160 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK9 %s
+// RUN: llvm-objdump -d %t2 -start-address=53477380 -stop-address=53477392 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK9 %s
 // RUN: llvm-objdump -d %t2 -start-address=68157440 -stop-address=68157452 -triple=armv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK10 %s
 // RUN: llvm-objdump -d %t2 -start-address=69206016 -stop-address=69206024 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK11 %s
 
 // Test the Range extension Thunks for ARM and Thumb when all the code is in a
 // single OutputSection. The ARM branches and branch and link instructions
 // have a range of 32Mb, the Thumb unconditional branch and
 // branch and link instructions have . We create a series of Functions a
 // megabyte apart. We expect range extension thunks to be created when a

 // CHECK8-NEXT:  2e00004:       01 c0 00 e3     movw    r12, #1
 // CHECK8-NEXT:  2e00008:       40 c2 40 e3     movt    r12, #576
 // CHECK8-NEXT:  2e0000c:       1c ff 2f e1     bx      r12
  ARMFUNCTION 46
  THUMBFUNCTION 47
  ARMFUNCTION 48
  THUMBFUNCTION 49
  ARMFUNCTION 50
+// Expect precreated Thunk Section here
+// CHECK9: __Thumbv7ABSLongThunk_afunc34:
+// CHECK9-NEXT:  3300004:       40 f2 00 0c     movw    r12, #0
+// CHECK9-NEXT:  3300008:       c0 f2 30 2c     movt    r12, #560
+// CHECK9-NEXT:  330000c:       60 47   bx      r12
+// CHECK9: __Thumbv7ABSLongThunk_tfunc35:
+// CHECK9-NEXT:  330000e:       ff f4 f7 97     b.w     #-15728658 <tfunc35>
  THUMBFUNCTION 51
  ARMFUNCTION 52
  THUMBFUNCTION 53
  ARMFUNCTION 54
  THUMBFUNCTION 55
  ARMFUNCTION 56
  THUMBFUNCTION 57
  ARMFUNCTION 58
  THUMBFUNCTION 59
  ARMFUNCTION 60
-// Expect precreated Thunk Section here
-// CHECK9: __Thumbv7ABSLongThunk_afunc34:
-// CHECK9-NEXT:  3d00004:       40 f2 00 0c     movw    r12, #0
-// CHECK9-NEXT:  3d00008:       c0 f2 30 2c     movt    r12, #560
-// CHECK9-NEXT:  3d0000c:       60 47   bx      r12
-// CHECK9: __Thumbv7ABSLongThunk_tfunc35:
-// CHECK9-NEXT:  3d0000e:       40 f2 01 0c     movw    r12, #1
-// CHECK9-NEXT:  3d00012:       c0 f2 40 2c     movt    r12, #576
-// CHECK9-NEXT:  3d00016:       60 47   bx      r12
  THUMBFUNCTION 61
  ARMFUNCTION 62
  THUMBFUNCTION 63
  ARMFUNCTION 64
 // afunc34 is in range, as is tfunc35 but a branch needs a state change Thunk
  bl afunc34
  b  tfunc35
 // CHECK10: afunc64:
 // CHECK10-NEXT:  4100000:       1e ff 2f e1     bx      lr
 // CHECK10-NEXT:  4100004:      fd ff 87 eb     bl      #-31457292 <afunc34>
 // CHECK10-NEXT:  4100008:      fd ff b3 ea     b       #-19922956 <__ARMv7ABSLongThunk_tfunc35>
  THUMBFUNCTION 65
 // afunc34 and tfunc35 are both out of range
  bl afunc34
  bl tfunc35
 // CHECK11: tfunc65:
 // CHECK11:  4200000:   70 47   bx      lr
-// CHECK11-NEXT:  4200002:      ff f6 ff f7     bl      #-5242882
-// CHECK11-NEXT:  4200006:      00 f7 02 f0     bl      #-5242876
+// CHECK11-NEXT:  4200002:      ff f4 ff d7     bl      #-15728642
+// CHECK11-NEXT:  4200006:      00 f5 02 d0     bl      #-15728636

lld/trunk/test/ELF/arm-thumb-range-thunk-os.s

 // REQUIRES: arm
 // RUN: llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi %s -o %t
 // RUN: ld.lld %t -o %t2 2>&1
 // The output file is large, most of it zeroes. We dissassemble only the
 // parts we need to speed up the test and avoid a large output file
 // RUN: llvm-objdump -d %t2 -start-address=1048576 -stop-address=1048588 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK1 %s
 // RUN: llvm-objdump -d %t2 -start-address=2097152 -stop-address=2097154 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK2 %s
 // RUN: llvm-objdump -d %t2 -start-address=3145728 -stop-address=3145730 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK3 %s
 // RUN: llvm-objdump -d %t2 -start-address=4194304 -stop-address=4194310 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK4 %s
 // RUN: llvm-objdump -d %t2 -start-address=16777216 -stop-address=16777270 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK5 %s
 // RUN: llvm-objdump -d %t2 -start-address=17825792 -stop-address=17825808 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK6 %s
-// RUN: llvm-objdump -d %t2 -start-address=31457280 -stop-address=31457286 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK7 %s
-// RUN: llvm-objdump -d %t2 -start-address=32505860 -stop-address=32505880 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK8 %s
+// RUN: llvm-objdump -d %t2 -start-address=20971524 -stop-address=20971532 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK7 %s
+// RUN: llvm-objdump -d %t2 -start-address=31457280 -stop-address=31457286 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK8 %s
 // RUN: llvm-objdump -d %t2 -start-address=35651584 -stop-address=35651594 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK9 %s
 // RUN: llvm-objdump -d %t2 -start-address=36700160 -stop-address=36700170 -triple=thumbv7a-linux-gnueabihf | FileCheck -check-prefix=CHECK10 %s
 
 // Test the Range extension Thunks for Thumb when all the code is in a single
 // OutputSection. The Thumb unconditional branch b.w and branch and link bl
 // instructions have a range of 16Mb. We create a series of Functions a
 // megabyte apart. We expect range extension thunks to be created when a
 // branch is out of range. Thunks will be reused whenever they are in range

 // CHECK6-NEXT:  1100000:       70 47   bx      lr
 // CHECK6-NEXT:  1100002:       ff f4 fd d7     bl      #-15728646
 // CHECK6-NEXT:  1100006:       ff f5 fb d7     bl      #-14680074
 // CHECK6-NEXT:  110000a:       ff f6 ff ff     bl      #-1048578
 // CHECK6-NEXT:  110000e:       00 f7 02 f8     bl      #-1048572
  FUNCTION 16
  FUNCTION 17
  FUNCTION 18
+// Expect another precreated thunk section here
+// CHECK7: __Thumbv7ABSLongThunk_tfunc15:
+// CHECK7-NEXT:  1400004:       ff f4 fc bf     b.w     #-3145736 <tfunc15>
+// CHECK7: __Thumbv7ABSLongThunk_tfunc16:
+// CHECK7-NEXT:  1400008:       ff f5 fa bf     b.w     #-2097164 <tfunc16>
  FUNCTION 19
  FUNCTION 20
  FUNCTION 21
  FUNCTION 22
  FUNCTION 23
  FUNCTION 24
  FUNCTION 25
  FUNCTION 26
  FUNCTION 27
  FUNCTION 28
 // tfunc02 is > 16Mb away, expect range extension thunks in precreated thunk
 // section
-// CHECK7:  tfunc28:
-// CHECK7-NEXT:  1e00000:       70 47   bx      lr
-// CHECK7-NEXT:  1e00002:       00 f6 0d 90     b.w     #-14680038 <__Thumbv7ABSLongThunk_tfunc02>
+// CHECK8:  tfunc28:
+// CHECK8-NEXT:  1e00000:       70 47   bx      lr
+// CHECK8-NEXT:  1e00002:       00 f6 0d 90     b.w     #-14680038 <__Thumbv7ABSLongThunk_tfunc02>
 
  b.w tfunc02
  FUNCTION 29
-// Expect another precreated thunk section here
-// CHECK8: __Thumbv7ABSLongThunk_tfunc15:
-// CHECK8-NEXT:  1f00004:       ff f5 fc 97     b.w     #-14680072 <tfunc15>
-// CHECK8: __Thumbv7ABSLongThunk_tfunc16:
-// CHECK8-NEXT:  1f00008:       ff f6 fa 97     b.w     #-13631500 <tfunc16>
  FUNCTION 30
  FUNCTION 31
  FUNCTION 32
  // tfunc15 and tfunc16 are > 16 Mb away expect Thunks in the nearest
  // precreated thunk section.
  bl tfunc15
  bl tfunc16
 // CHECK9: tfunc32:
 // CHECK9:  2200000:    70 47   bx      lr
-// CHECK9-NEXT:  2200002:       ff f4 ff ff     bl      #-3145730
-// CHECK9-NEXT:  2200006:       ff f4 ff ff     bl      #-3145730
+// CHECK9-NEXT:  2200002:       ff f5 ff d7     bl      #-14680066
+// CHECK9-NEXT:  2200006:       ff f5 ff d7     bl      #-14680066
 
  FUNCTION 33
  bl tfunc15
  bl tfunc16
 // CHECK10: tfunc33:
 // CHECK10:  2300000:   70 47   bx      lr
-// CHECK10-NEXT:  2300002:      ff f7 ff f7     bl      #-4194306
-// CHECK10-NEXT:  2300006:      ff f7 ff f7     bl      #-4194306
+// CHECK10-NEXT:  2300002:      ff f4 ff d7     bl      #-15728642
+// CHECK10-NEXT:  2300006:      ff f4 ff d7     bl      #-15728642