[ELF] Fix branch range computation when picking ThunkSection

Similar to D117734. Take AArch64 as an example when the branch range is +-0x8000000.

getISDThunkSec returns `ts` when `src-0x8000000-r_addend <= tsBase < src-0x8000000`
and the new thunk will be placed in `ts` (`ts->addThunk(t)`). However, the new
thunk (at the end of ts) may be unreachable from src. In the next pass,
`normalizeExistingThunk` reverts the relocation back to the original target.
Then a new thunk is created and the same `ts` is picked as before. The `ts` is
still unreachable.

I have observed it in one test with a sufficiently large r_addend (47664): there
are initially 245 Thunk's, then in each pass 14 new Thunk's are created and get
appended to the unreachable ThunkSection. After 15 passes lld fails with
`thunk creation not converged`.

The new test aarch64-thunk-reuse2.s checks the case.

Without `- pcBias`, arm-thumb-thunk-empty-pass.s and arm-thunk-multipass-plt.s
will fail.

Reviewed By: peter.smith

Differential Revision: https://reviews.llvm.org/D124653

2 files changed, 55 insertions, 15 deletions

diff --git a/lld/ELF/Relocations.cpp b/lld/ELF/Relocations.cpp
index ed1f2168170d..0ba761728442 100644
--- a/lld/ELF/Relocations.cpp
+++ b/lld/ELF/Relocations.cpp
@@ -1862,6 +1862,19 @@ void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) {
       });
 }
 
+static int64_t getPCBias(RelType type) {
+  if (config->emachine != EM_ARM)
+    return 0;
+  switch (type) {
+  case R_ARM_THM_JUMP19:
+  case R_ARM_THM_JUMP24:
+  case R_ARM_THM_CALL:
+    return 4;
+  default:
+    return 8;
+  }
+}
+
 // Find or create a ThunkSection within the InputSectionDescription (ISD) that
 // is in range of Src. An ISD maps to a range of InputSections described by a
 // linker script section pattern such as { .text .text.* }.
@@ -1870,10 +1883,12 @@ ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os,
                                            InputSectionDescription *isd,
                                            const Relocation &rel,
                                            uint64_t src) {
+  // See the comment in getThunk for -pcBias below.
+  const int64_t pcBias = getPCBias(rel.type);
   for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) {
     ThunkSection *ts = tp.first;
-    uint64_t tsBase = os->addr + ts->outSecOff + rel.addend;
-    uint64_t tsLimit = tsBase + ts->getSize() + rel.addend;
+    uint64_t tsBase = os->addr + ts->outSecOff - pcBias;
+    uint64_t tsLimit = tsBase + ts->getSize();
     if (target->inBranchRange(rel.type, src,
                               (src > tsLimit) ? tsBase : tsLimit))
       return ts;
@@ -2024,19 +2039,6 @@ static bool isThunkSectionCompatible(InputSection *source,
   return true;
 }
 
-static int64_t getPCBias(RelType type) {
-  if (config->emachine != EM_ARM)
-    return 0;
-  switch (type) {
-  case R_ARM_THM_JUMP19:
-  case R_ARM_THM_JUMP24:
-  case R_ARM_THM_CALL:
-    return 4;
-  default:
-    return 8;
-  }
-}
-
 std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec,
                                                 Relocation &rel, uint64_t src) {
   std::vector<Thunk *> *thunkVec = nullptr;
diff --git a/lld/test/ELF/aarch64-thunk-reuse2.s b/lld/test/ELF/aarch64-thunk-reuse2.s
new file mode 100644
index 000000000000..6495f8a5284b
--- /dev/null
+++ b/lld/test/ELF/aarch64-thunk-reuse2.s
@@ -0,0 +1,38 @@
+# REQUIRES: aarch64
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %s -o %t.o
+# RUN: ld.lld -pie -Ttext=0x10300 %t.o -o %t
+# RUN: llvm-objdump -d --no-show-raw-insn --disassemble-symbols=dest,__AArch64ADRPThunk_,high %t | FileCheck %s
+
+## We create initial ThunkSection before the gap. Because the ThunkSection
+## selection code isn't so precise, we may create an unused thunk there (0x10704).
+## In the next pass we will create a ThunkSection after the gap. There used to be
+## a bug reusing the first ThunkSection (unreachable) due to the large r_addend.
+# CHECK:       <dest>:
+# CHECK-NEXT:     10700:       ret
+# CHECK:       <__AArch64ADRPThunk_>:
+# CHECK-NEXT:     10704:       adrp    x16, 0x10000
+# CHECK-NEXT:                  add     x16, x16, #1792
+# CHECK-NEXT:                  br      x16
+# CHECK-EMPTY:
+# CHECK:       <__AArch64ADRPThunk_>:
+# CHECK-NEXT:   8010710:       adrp    x16, 0x10000
+# CHECK-NEXT:                  add     x16, x16, #1792
+# CHECK-NEXT:                  br      x16
+# CHECK-LABEL: <high>:
+# CHECK-NEXT:   801071c:       bl      0x8010710 <__AArch64ADRPThunk_>
+# CHECK-NEXT:                  b       0x8010710 <__AArch64ADRPThunk_>
+
+.section .text._start, "ax", %progbits
+.globl _start
+_start:
+.space 0x400
+dest:
+  ret
+
+.section .text.gap, "ax", %progbits
+.space 0x8000000
+
+.section .text.high, "ax", %progbits
+high:
+  bl dest
+  b dest