[LLD][ELF][AArch64] Add AArch64 short range thunk support

[peter.smith]

Summary

The AArch64 branch immediate instruction has a 128MiB range. This makes it suitable for use a short range thunk in the same way as short thunks are implemented in Arm and PPC. This patch adds support for short range thunks to AArch64.

Adding short range thunk support should mean that OutputSections can grow to nearly 256 MiB in size without needing long-range indirect branches.

[MaskRay]

Thanks for the patch. AArch64ADRPThunk and AArch64ABSLongThunk duplicate writeTo and getMayUseShortThunk now. Shall we define a base class for the two classes to share code?

This makes it suitable for use a short range thunk in the same way as short thunks are implemented in Arm and PPC.

Is Arm ambiguous here? AArch32 and PPC64?

---

Is there any analysis how frequently this short thunk mode is going to trigger?

We need a thunk for b far or bl far. By using a b instruction, we can reach from +-128MiB at the thunk section location (instead of the original call site).
This does not guarantee a 256MiB range without indirect branches, as we don't necessarily place the thunk 128MiB from the call site.
This is in part because ThunkCreator::getThunk picks the first available thunk, not the best one.

Let's use aarch64-call26-thunk.s as an example. If I change Inputs/abs.s to use big = 0x8210120 (shorter addresses don't need a thunk), I'll get a short range thunk. If I use big = 0x8210124 or higher, I'll get a long range thunk.

[MaskRay]

I can check how to try improving ThunkCreator::getThunk. We will likely need a more powerful API than target->inBranchRange to get the distance, not just a binary result.

[peter.smith]

In D148701#4281776, @MaskRay wrote:

Thanks for the patch. AArch64ADRPThunk and AArch64ABSLongThunk duplicate writeTo and getMayUseShortThunk now. Shall we define a base class for the two classes to share code?

That is possible as the short branch code will be the same in both cases. It was one of the cases where for two cases the duplication may end up simpler than a base class, but if there were 3 or more it wouldn't. I can certainly change that.

This makes it suitable for use a short range thunk in the same way as short thunks are implemented in Arm and PPC.

Is Arm ambiguous here? AArch32 and PPC64?

I meant this uses the same strategy of using a branch as the ARM/Thumb (AArch32) thunks and I think PPC64.

---

Is there any analysis how frequently this short thunk mode is going to trigger?

The vast majority of user-space AArch64 programs need no range-extension thunks at all as the executable segment is contiguous and smaller than 128 MiB. We have seen a small number of programs in the 128 MiB to 256 Mib such as a fully instrumented Chromium build, some Haskell programs also get this large naturally. For programs in this size range with a contiguous text segment I'd expect short thunks to replace the larger ones.

I would not expect it to trigger for linker scripts that separate the code into separate disjoint OutputSections.

We need a thunk for b far or bl far. By using a b instruction, we can reach from +-128MiB at the thunk section location (instead of the original call site).
This does not guarantee a 256MiB range without indirect branches, as we don't necessarily place the thunk 128MiB from the call site.
This is in part because ThunkCreator::getThunk picks the first available thunk, not the best one.

Let's use aarch64-call26-thunk.s as an example. If I change Inputs/abs.s to use big = 0x8210120 (shorter addresses don't need a thunk), I'll get a short range thunk. If I use big = 0x8210124 or higher, I'll get a long range thunk.

The way code is written today is not optimal for short thunks but it can work reasonably well for large contiguous OutputSections like a .text. The initial pools are spaced at roughly branch-range intervals, so in a 256 MiB .text OutputSection there will be two pools, one roughly central. Callers at the start of the .text section to a destination near the end can nearly double their range, although the closer a caller gets to a pool the lower the benefits of range extension.

Arm's proprietary linker armlink has a much more complicated thunk assignment algorithm. Essentially it works out from the callers addresses and the destination address what the valid address range for the thunk insertion is and uses the mid-point of that range. This does have its drawbacks as while the address ranges are close to continuous, the valid insertion points in between sections are not so we can end up with the only valid insertion points being in the middle of a section, which requires special case code. All possible, but quite a lot more complexity. It also makes the binary layout a lot messier and harder to predict as thunks are scattered around the image.

I'll send an update with a base class. My summary is that I think that this will help programs of the 128 MiB to 256 MiB in a single .text OutputSection. Most likely a small handful of programs to date though. They are much more useful on Arm (Thumb) as many programs are larger than 16 MiB.

[peter.smith]

Use base class to share code for Short Branch functionality.

[tschuett]

lld/ELF/Thunks.cpp

75

Either virtual or override, but never both. In this case you want override.

[peter.smith]

Remove spurious virtual from declaration.

lld/ELF/Thunks.cpp

75

Thanks for spotting and apologies for missing that. Will fix.

[MaskRay]

Thanks for the update. With the base class, the number of lines have decreased by 4 even with the long comment "An AArch64 thunk may be either short or long ...", so the base class looks worthwhile!

lld/ELF/Thunks.cpp

57–58

It seems more conventional to place constructors before member functions.

lld/test/ELF/aarch64-long-thunk-converge.s

7

Perhaps remove %t/a after the link. It is very large (420MiB).

9

The paragraphs uses several spellings for a long thunk: long-thunk, long-range thunk, and long range thunk. Canonicalize them?

12

Our pass variable starts with 0.

/ In pass 0, bl foo requires a long-range thunk to reach foo. The thunk for bar increases the address of foo so that it can be reached by bl foo with a single b instruction.
/ In pass 1, we expect the long-range thunk for bl foo to remain long.

17

[peter.smith]

Thanks for the review. I've uploaded a new diff with the suggestions.

[peter.smith]

Review comments prior to commit.

lld/ELF/Thunks.cpp

 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 using namespace lld;
 using namespace lld::elf;
 
 namespace {
 
-// AArch64 long range Thunks
-class AArch64ABSLongThunk final : public Thunk {
+// Base class for AArch64 thunks.
+//
+// An AArch64 thunk may be either short or long. A short thunk is simply a
+// branch (B) instruction, and it may be used to call AArch64 functions when the
+// distance from the thunk to the target is less than 128MB. Long thunks can
+// branch to any virtual address and they are implemented in the derived
+// classes. This class tries to create a short thunk if the target is in range,
+// otherwise it creates a long thunk.
+class AArch64Thunk : public Thunk {
 public:
-  AArch64ABSLongThunk(Symbol &dest, int64_t addend) : Thunk(dest, addend) {}
-  uint32_t size() override { return 16; }
+  AArch64Thunk(Symbol &dest, int64_t addend) : Thunk(dest, addend) {}
+  bool getMayUseShortThunk();
   void writeTo(uint8_t *buf) override;
+
+private:
+  bool mayUseShortThunk = true;
+  virtual void writeLong(uint8_t *buf) = 0;
+};
+
+// AArch64 long range Thunks.
+class AArch64ABSLongThunk final : public AArch64Thunk {
+public:
+  AArch64ABSLongThunk(Symbol &dest, int64_t addend)
+      : AArch64Thunk(dest, addend) {}
+  uint32_t size() override { return getMayUseShortThunk() ? 4 : 16; }
   void addSymbols(ThunkSection &isec) override;
+
+private:
+  void writeLong(uint8_t *buf) override;
 };
 
-class AArch64ADRPThunk final : public Thunk {
+class AArch64ADRPThunk final : public AArch64Thunk {
 public:
-  AArch64ADRPThunk(Symbol &dest, int64_t addend) : Thunk(dest, addend) {}
-  uint32_t size() override { return 12; }
-  void writeTo(uint8_t *buf) override;
+  AArch64ADRPThunk(Symbol &dest, int64_t addend) : AArch64Thunk(dest, addend) {}
+  uint32_t size() override { return getMayUseShortThunk() ? 4 : 12; }
   void addSymbols(ThunkSection &isec) override;
+
+private:
+  void writeLong(uint8_t *buf) override;
 };
 
 // Base class for ARM thunks.
 //
 // An ARM thunk may be either short or long. A short thunk is simply a branch
 // (B) instruction, and it may be used to call ARM functions when the distance
 // from the thunk to the target is less than 32MB. Long thunks can branch to any
 // virtual address and can switch between ARM and Thumb, and they are

 }
 
 void Thunk::setOffset(uint64_t newOffset) {
   for (Defined *d : syms)
     d->value = d->value - offset + newOffset;
   offset = newOffset;
 }
 
-// AArch64 long range Thunks
-
+// AArch64 Thunk base class.
 static uint64_t getAArch64ThunkDestVA(const Symbol &s, int64_t a) {
   uint64_t v = s.isInPlt() ? s.getPltVA() : s.getVA(a);
   return v;
 }
 
-void AArch64ABSLongThunk::writeTo(uint8_t *buf) {
+bool AArch64Thunk::getMayUseShortThunk() {
+  if (!mayUseShortThunk)
+    return false;
+  uint64_t s = getAArch64ThunkDestVA(destination, addend);
+  uint64_t p = getThunkTargetSym()->getVA();
+  mayUseShortThunk = llvm::isInt<28>(s - p);
+  return mayUseShortThunk;
+}
+
+void AArch64Thunk::writeTo(uint8_t *buf) {
+  if (!getMayUseShortThunk()) {
+    writeLong(buf);
+    return;
+  }
+  uint64_t s = getAArch64ThunkDestVA(destination, addend);
+  uint64_t p = getThunkTargetSym()->getVA();
+  write32(buf, 0x14000000); // b S
+  target->relocateNoSym(buf, R_AARCH64_CALL26, s - p);
+}
+
+// AArch64 long range Thunks.
+void AArch64ABSLongThunk::writeLong(uint8_t *buf) {
   const uint8_t data[] = {
     0x50, 0x00, 0x00, 0x58, //     ldr x16, L0
     0x00, 0x02, 0x1f, 0xd6, //     br  x16
     0x00, 0x00, 0x00, 0x00, // L0: .xword S
     0x00, 0x00, 0x00, 0x00,
   };
   uint64_t s = getAArch64ThunkDestVA(destination, addend);
   memcpy(buf, data, sizeof(data));
   target->relocateNoSym(buf + 8, R_AARCH64_ABS64, s);
 }
 
 void AArch64ABSLongThunk::addSymbols(ThunkSection &isec) {
   addSymbol(saver().save("__AArch64AbsLongThunk_" + destination.getName()),
             STT_FUNC, 0, isec);
   addSymbol("$x", STT_NOTYPE, 0, isec);
+  if (!getMayUseShortThunk())
     addSymbol("$d", STT_NOTYPE, 8, isec);
 }
 
 // This Thunk has a maximum range of 4Gb, this is sufficient for all programs
 // using the small code model, including pc-relative ones. At time of writing
 // clang and gcc do not support the large code model for position independent
 // code so it is safe to use this for position independent thunks without
 // worrying about the destination being more than 4Gb away.
-void AArch64ADRPThunk::writeTo(uint8_t *buf) {
+void AArch64ADRPThunk::writeLong(uint8_t *buf) {
   const uint8_t data[] = {
       0x10, 0x00, 0x00, 0x90, // adrp x16, Dest R_AARCH64_ADR_PREL_PG_HI21(Dest)
       0x10, 0x02, 0x00, 0x91, // add  x16, x16, R_AARCH64_ADD_ABS_LO12_NC(Dest)
       0x00, 0x02, 0x1f, 0xd6, // br   x16
   };
   uint64_t s = getAArch64ThunkDestVA(destination, addend);
   uint64_t p = getThunkTargetSym()->getVA();
   memcpy(buf, data, sizeof(data));

lld/test/ELF/aarch64-cortex-a53-843419-thunk.s

 // REQUIRES: aarch64
 // RUN: llvm-mc -filetype=obj -triple=aarch64-none-linux %s -o %t.o
 // RUN: echo "SECTIONS { \
 // RUN:          .text1 0x10000 : { *(.text.01) *(.text.02) *(.text.03) } \
-// RUN:          .text2 0x8010000 : { *(.text.04) } } " > %t.script
+// RUN:          .text2 0x10010000 : { *(.text.04) } } " > %t.script
 // RUN: ld.lld --script %t.script -fix-cortex-a53-843419 -verbose %t.o -o %t2 \
 // RUN:   2>&1 | FileCheck -check-prefix=CHECK-PRINT %s
 // RUN: llvm-objdump --no-print-imm-hex --no-show-raw-insn --triple=aarch64-linux-gnu -d %t2 | FileCheck %s
 
 /// %t2 is 128 Megabytes, so delete it early.
 // RUN: rm %t2
 
 /// Test cases for Cortex-A53 Erratum 843419 that involve interactions with

 t3_ff8_ldr:
         adrp x0, dat
         ldr x1, [x1, #0]
         ldr x0, [x0, :got_lo12:dat]
         ret
 
 // CHECK-PRINT: detected cortex-a53-843419 erratum sequence starting at 10FF8 in unpatched output.
 // CHECK: 0000000000010ff8 <t3_ff8_ldr>:
-// CHECK-NEXT: adrp    x0, 0x8010000
+// CHECK-NEXT: adrp    x0, 0x10010000
 // CHECK-NEXT: ldr     x1, [x1]
 // CHECK-NEXT: b       0x11008
 // CHECK-NEXT: ret
 // CHECK: 0000000000011008 <__CortexA53843419_11000>:
 // CHECK-NEXT: ldr     x0, [x0, #8]
 // CHECK-NEXT: b       0x11004
         .section .text.04, "ax", %progbits
         .globl far_away
         .type far_away, function
 far_away:
         ret
 
         .section .data
         .globl dat
 dat:    .quad 0

lld/test/ELF/aarch64-long-thunk-converge.s

+// REQUIRES: aarch64
+// RUN: rm -rf %t && split-file %s %t
+// RUN: llvm-mc -triple aarch64-none-elf -filetype=obj -o %t/a.o %t/a.s
+// RUN: ld.lld --shared %t/a.o -T %t/a.t -o %t/a
+// RUN: llvm-objdump --no-show-raw-insn -d --start-address=0x7001004 --stop-address=0x7001010 %t/a | FileCheck %s
+// RUN: llvm-objdump --no-show-raw-insn -d --start-address=0x11001008 --stop-address=0x11001014 %t/a | FileCheck --check-prefix=CHECK2 %s
+// RUN: rm -f %t/a
+/// This test shows that once a long-range thunk has been generated it
+/// cannot be written as a short-range thunk. This prevents oscillations
+/// in size that can prevent convergence.
+/// In pass 0 bl foo requires a long-range thunk to reach foo. The thunk for
+/// bar increases the address of foo so that ic can be reaced by bl foo with a
+/// a single b instruction.
+/// In pass 2 we expect the the long-range thunk to remain long.
+
+// CHECK-LABEL: <__AArch64ADRPThunk_>:
+// CHECK-NEXT: 7001004: adrp    x16, 0x11001000
+// CHECK-NEXT:          add     x16, x16, #0x14
+// CHECK-NEXT:          br      x16
+
+// CHECK2-LABEL: <__AArch64ADRPThunk_>:
+// CHECK2-NEXT: 11001008: adrp    x16, 0x9001000
+// CHECK2-NEXT:           add     x16, x16, #0x10
+// CHECK2-NEXT:           br      x16
+
+
+//--- a.t
+SECTIONS {
+  .foo 0x1000 : { *(.foo.*) }
+  .bar 0x11001000 : { *(.bar.*) }
+}
+
+//--- a.s
+.section .foo.1,"ax",%progbits,unique,1
+bl bar
+
+.section .foo.2,"ax",%progbits,unique,1
+.space 0x7000000
+
+.section .foo.3,"ax",%progbits,unique,1
+.space 0x2000000
+
+.section .foo.4,"ax",%progbits,unique,1
+foo:
+nop
+
+.section .bar.1,"ax",%progbits,unique,1
+nop
+nop
+.section .bar.2,"ax",%progbits,unique,1
+bar:
+bl foo
+.space 0x8000000

lld/test/ELF/aarch64-thunk-reuse2.s

 # 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 --no-print-imm-hex -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-NEXT:     10704:       b       0x10700 <dest>
 # CHECK-EMPTY:
 # CHECK:       <__AArch64ADRPThunk_>:
-# CHECK-NEXT:   8010710:       adrp    x16, 0x10000
+# CHECK-NEXT:   8010708:       adrp    x16, 0x10000
 # CHECK-NEXT:                  add     x16, x16, #1792
-# CHECK-NEXT:                  br      x16
+# CHECk-NEXT:                  br      x16
 # CHECK-LABEL: <high>:
-# CHECK-NEXT:   801071c:       bl      0x8010710 <__AArch64ADRPThunk_>
-# CHECK-NEXT:                  b       0x8010710 <__AArch64ADRPThunk_>
+# CHECK-NEXT:   8010714:       bl      0x8010708 <__AArch64ADRPThunk_>
+# CHECK-NEXT:                  b       0x8010708 <__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

lld/test/ELF/aarch64-thunk-script.s

  // No Thunk needed as we are within signed immediate range
  bl _start
  ret
 
 // CHECK: Disassembly of section .text_low:
 // CHECK-EMPTY:
 // CHECK-NEXT: <_start>:
 // CHECK-NEXT:     2000:       bl      0x200c <__AArch64AbsLongThunk_high_target>
-// CHECK-NEXT:     2004:       bl      0x201c <__AArch64AbsLongThunk_>
+// CHECK-NEXT:     2004:       bl      0x2010 <__AArch64AbsLongThunk_>
 // CHECK-NEXT:                 ret
 // CHECK: <__AArch64AbsLongThunk_high_target>:
-// CHECK-NEXT:     200c:       ldr     x16, 0x2014
-// CHECK-NEXT:                 br      x16
-// CHECK: <$d>:
-// CHECK-NEXT:     2014:       00 20 00 08     .word   0x08002000
-// CHECK-NEXT:     2018:       00 00 00 00     .word   0x00000000
-// CHECK:      <__AArch64AbsLongThunk_>:
-// CHECK-NEXT:     201c:       ldr x16, 0x2024
-// CHECK-NEXT:     2020:       br x16
-// CHECK:      <$d>:
-// CHECK-NEXT:     2024:       04 20 00 08     .word   0x08002004
-// CHECK-NEXT:     2028:       00 00 00 00     .word   0x00000000
+// CHECK-NEXT:     200c:       b       0x8002000 <high_target>
+// CHECK: <__AArch64AbsLongThunk_>:
+// CHECK-NEXT:     2010:       b       0x8002004 <high_target+0x4>
 // CHECK: Disassembly of section .text_high:
 // CHECK-EMPTY:
 // CHECK-NEXT: <high_target>:
 // CHECK-NEXT:  8002000:       bl      0x2000 <_start>
 // CHECK-NEXT:                 ret
 
 /// Local symbols copied from %t.o
 // NM:      t $x.0
 // NM-NEXT: t $x.1
 /// Local thunk symbols.
 // NM-NEXT: t __AArch64AbsLongThunk_high_target
 // NM-NEXT: t $x
-// NM-NEXT: t $d
 // NM-NEXT: t __AArch64AbsLongThunk_{{$}}
 // NM-NEXT: t $x
-// NM-NEXT: t $d
 /// Global symbols.
 // NM-NEXT: T _start
 // NM-NEXT: T high_target
 
 //--- lds
 PHDRS {
   low PT_LOAD FLAGS(0x1 | 0x4);
   high PT_LOAD FLAGS(0x1 | 0x4);
 }
 SECTIONS {
   .text_low 0x2000: { *(.text_low) } :low
   .text_high 0x8002000 : { *(.text_high) } :high
 }

lld/test/ELF/aarch64-thunk-section-location.s

 // REQUIRES: aarch64
 // RUN: llvm-mc -filetype=obj -triple=aarch64-linux-gnu %s -o %t.o
 // RUN: ld.lld %t.o -o %t
-// RUN: llvm-objdump -d --start-address=0x81d1008 --stop-address=0x81d1014 --no-show-raw-insn %t | FileCheck %s
+// RUN: llvm-objdump -d --start-address=0x81d1008 --stop-address=0x81d100c --no-show-raw-insn %t | FileCheck %s
 // RUN: rm %t.o %t
 // Check that the range extension thunks are dumped close to the aarch64 branch
 // range of 128 MiB
  .section .text.1, "ax", %progbits
  .balign 0x1000
  .globl _start
 _start:
  bl high_target

  .balign 0x1000
 
  .globl high_target
  .type high_target, %function
 high_target:
  ret
 
 // CHECK: <__AArch64AbsLongThunk_high_target>:
-// CHECK-NEXT:  81d1008:       ldr     x16, 0x81d1010
-// CHECK-NEXT:  81d100c:       br      x16
-// CHECK: <$d>:
-// CHECK-NEXT:  81d1010:       00 20 21 08     .word   0x08212000
+// CHECK-NEXT: 81d1008:       b       0x8212000 <high_target>