[LLD][PowerPC] Add a pc-rel based long branch thunk

[NeHuang]

Summary

In this patch, a pc-rel based long branch thunk is added for the local call protocol that caller and callee does not use TOC.

[sfertile]

lld/ELF/Thunks.cpp

375

IIUC If there is a call between a pc-rel based caller and a toc-based callee (so that callee has global and local entry points) then we will have emitted an PPC64R12SetupoStub. Likewise, if its a toc-based caller and pc-rel based callee we use an R2SaveStub. So its only between pc-rel based caller and callee that we can have a pc rel based long branch thunk.

993

The R12Setup stub calculates the address of the callee relative to the program counter.

writePrefixedInstruction(buf + 0, paddi); // paddi r12, 0, func@pcrel, 1
write32(buf + 8, MTCTR_R12);              // mtctr r12
write32(buf + 12, BCTR);                  // bctr

The toc-based long branch thunks have to use a table in the data segment because of limited address-ability. The pc-rel instructions and ABI doesn't have the same limitation, so why use the branch linkage table intead of doing the same thing the R12Setup stubs do?

[NeHuang]

lld/ELF/Thunks.cpp

375

Yes. PC-Rel based long branch thunk is needed only between pc-rel based caller and callee.

• PC-Rel based caller and toc-based callee will use PPC64R12SetupStub
• Toc-based caller and pc-rel based callee will use PPC64R2SaveStub

993

Good point! Will update the patch without using branch_lt table.

[NeHuang]

Update the patch without using branch_lt table.

[nemanjai]

lld/ELF/Thunks.cpp

993

Is it not possible to need a long branch to a destination that isn't available yet? I thought that something like the following would require a long branch to a PLT stub:

#include <stdio.h>
int main(int argc, const char **argv) {
  int a = argc;
  printf("a = %d\n", a);
  asm (".space 134217728");
  printf("a = %d\n", a);
}

But that seems to create two PLT stubs. Is this something that always happens? Namely, is it always the case that the linker will never create a thunk that goes to another thunk? If so, I think a comment explaining that might be useful.

[NeHuang]

lld/ELF/Thunks.cpp

993

IIUC we only create a long branch thunk between a caller and callee and we check if there is a valid RelType (R_PPC64_REL14, R_PPC64_REL24, R_PPC64_REL24_NOTOC) in PPC64::needsThunk

[sfertile]

lld/ELF/Thunks.cpp

993

is it always the case that the linker will never create a thunk that goes to another thunk.

getThunk looks at the symbol referenced by the relocation and sees if an existing compatible thunk can be reused, but if none fit the cirteria it creates a new thunk targeting the symbol rather then creating a thunk that targets another thunk.

Is it not possible to need a long branch to a destination that isn't available yet?

No: all the address sensitive content has been laid out and finalized by the time the thinks writeTo member function is called.

994

I don't believe we have accounted for the addend in the other PPC64 thunks (both toc-based and pc-rel based). If we do take into account the addend then we have to account for that in 'isCompatableWith' as well. I don't believe the compilers emit calls instructions using both symbol and addends (or we likely would have realized this earlier). I suggest to keep it simple we follow the example of the other thinks and omit the addend, or potentially error on a non-zero addend. We can then revisit this in a subsequent patch where we fix all the thunks that will need to account for the addend.

[NeHuang]

lld/ELF/Thunks.cpp

994

Agree, will omit the addend in this thunk o be consistent with other PPC64 thunks, we can fix all the thunks to account for the addend in a subsequent patch.

[sfertile]

One minor nit, but otherwise LGTM. If Nemanja would still like the comment he suggested make sure to address that before committing.

lld/ELF/Thunks.cpp

996

Real minor nit: mcmodel=large is a helpful hint, but I think its only relevant if you are using a C/C++ compiler and maybe fortran. It might be confusing if you are linking objects that came from a different source language.

[NeHuang]

Address Sean's comment for fatal error message.

[NeHuang]

lld/ELF/Thunks.cpp

996

Thanks, message updated.

[NeHuang]

Updated fatal error message in the LIT test

[MaskRay]

lld/ELF/Thunks.cpp

1143

How is the new PPC64PCRelLongBranchThunk different from PPC64R12SetupStub? Why can't the two be unified?

[NeHuang]

lld/ELF/Thunks.cpp

1143

They are identical. We will create a NFC patch to unify them. Thanks!

[MaskRay]

lld/ELF/Thunks.cpp

1143

I created D114656

lld/ELF/Thunks.cpp

public:
   void writeTo(uint8_t *buf) override;
   void addSymbols(ThunkSection &isec) override;
   bool isCompatibleWith(const InputSection &isec,
                         const Relocation &rel) const override;
 };
 
 // A bl instruction uses a signed 24 bit offset, with an implicit 4 byte
 // alignment. This gives a possible 26 bits of 'reach'. If the call offset is
-// larger then that we need to emit a long-branch thunk. The target address
+// larger than that we need to emit a long-branch thunk. The target address
 // of the callee is stored in a table to be accessed TOC-relative. Since the
 // call must be local (a non-local call will have a PltCallStub instead) the
 // table stores the address of the callee's local entry point. For
 // position-independent code a corresponding relative dynamic relocation is
 // used.
 class PPC64LongBranchThunk : public Thunk {
 public:
   uint32_t size() override { return 16; }
   void writeTo(uint8_t *buf) override;
   void addSymbols(ThunkSection &isec) override;
+  bool isCompatibleWith(const InputSection &isec,
+                        const Relocation &rel) const override;
 
 protected:
   PPC64LongBranchThunk(Symbol &dest, int64_t addend) : Thunk(dest, addend) {}
 };
 
 class PPC64PILongBranchThunk final : public PPC64LongBranchThunk {
 public:
   PPC64PILongBranchThunk(Symbol &dest, int64_t addend)

 class PPC64PDLongBranchThunk final : public PPC64LongBranchThunk {
 public:
   PPC64PDLongBranchThunk(Symbol &dest, int64_t addend)
       : PPC64LongBranchThunk(dest, addend) {
     in.ppc64LongBranchTarget->addEntry(&dest, addend);
   }
 };
 
+// A bl instruction uses a signed 24 bit offset, with an implicit 4 byte
+// alignment. This gives a possible 26 bits of 'reach'. If the call offset is
+// larger than that we need to emit a long-branch thunk. The target address
+// of the callee is stored in a table to be accessed PC-relative. Since the
+// call must be local (a non-local call will have a PCRelPltCallStub instead)
+// the table stores the address of the callee's local entry point. For
+// position-independent code a corresponding relative dynamic relocation is
+// used.
+class PPC64PCRelLongBranchThunk : public Thunk {
+public:
+  uint32_t size() override { return 16; }
+  void writeTo(uint8_t *buf) override;
+  void addSymbols(ThunkSection &isec) override;
+  bool isCompatibleWith(const InputSection &isec,
+                        const Relocation &rel) const override;
+
+protected:
+  PPC64PCRelLongBranchThunk(Symbol &dest, int64_t addend)
+      : Thunk(dest, addend) {
+    alignment = 16;
+  }
+};
+
+class PPC64PCRelPILongBranchThunk final : public PPC64PCRelLongBranchThunk {
+public:
+  PPC64PCRelPILongBranchThunk(Symbol &dest, int64_t addend)
+      : PPC64PCRelLongBranchThunk(dest, addend) {
+    assert(!dest.isPreemptible);
+    if (Optional<uint32_t> index =
+            in.ppc64LongBranchTarget->addEntry(&dest, addend)) {
+      mainPart->relaDyn->addReloc(
+          {target->relativeRel, in.ppc64LongBranchTarget, *index * UINT64_C(8),
+           true, &dest,
+           addend + getPPC64GlobalEntryToLocalEntryOffset(dest.stOther)});
+    }
+  }
+};
+
+class PPC64PCRelPDLongBranchThunk final : public PPC64PCRelLongBranchThunk {
+public:
+  PPC64PCRelPDLongBranchThunk(Symbol &dest, int64_t addend)
+      : PPC64PCRelLongBranchThunk(dest, addend) {
+    in.ppc64LongBranchTarget->addEntry(&dest, addend);
+  }
+};
+
 } // end anonymous namespace
 
 Defined *Thunk::addSymbol(StringRef name, uint8_t type, uint64_t value,
                           InputSectionBase &section) {
   Defined *d = addSyntheticLocal(name, type, value, /*size=*/0, section);
   syms.push_back(d);
   return d;
 }
void PPC64LongBranchThunk::writeTo(uint8_t *buf) {
   writePPC64LoadAndBranch(buf, offset);
 }
 
 void PPC64LongBranchThunk::addSymbols(ThunkSection &isec) {
   addSymbol(saver.save("__long_branch_" + destination.getName()), STT_FUNC, 0,
             isec);
 }
 
+bool PPC64LongBranchThunk::isCompatibleWith(const InputSection &isec,
+                                            const Relocation &rel) const {
+  return rel.type == R_PPC64_REL24 || rel.type == R_PPC64_REL14;
+}
+
+void PPC64PCRelLongBranchThunk::writeTo(uint8_t *buf) {
+  int64_t offset = in.ppc64LongBranchTarget->getEntryVA(&destination, addend) -
+                   getThunkTargetSym()->getVA();
+  if (!isInt<34>(offset))
+    fatal("offset overflow 34 bits, use large code model with mcmodel=large");
+  uint64_t pld =
+      PLD_R12_NO_DISP | (((offset >> 16) & 0x3ffff) << 32) | (offset & 0xffff);
+  writePrefixedInstruction(buf + 0, pld); // pld r12, func@branch_lt@pcrel
+  write32(buf + 8, MTCTR_R12);            // mtctr r12
+  write32(buf + 12, BCTR);                // bctr
+}
+
+void PPC64PCRelLongBranchThunk::addSymbols(ThunkSection &isec) {
+  addSymbol(saver.save("__long_branch_pcrel_" + destination.getName()),
+            STT_FUNC, 0, isec);
+}
+
+bool PPC64PCRelLongBranchThunk::isCompatibleWith(const InputSection &isec,
+                                                 const Relocation &rel) const {
+  return rel.type == R_PPC64_REL24_NOTOC;
+}
+
 Thunk::Thunk(Symbol &d, int64_t a) : destination(d), addend(a), offset(0) {}
 
 Thunk::~Thunk() = default;
 
 static Thunk *addThunkAArch64(RelType type, Symbol &s, int64_t a) {
   if (type != R_AARCH64_CALL26 && type != R_AARCH64_JUMP26 &&
       type != R_AARCH64_PLT32)
     fatal("unrecognized relocation type");
static Thunk *addThunkPPC64(RelType type, Symbol &s, int64_t a) {
   assert((type == R_PPC64_REL14 || type == R_PPC64_REL24 ||
           type == R_PPC64_REL24_NOTOC) &&
          "unexpected relocation type for thunk");
   if (s.isInPlt())
     return type == R_PPC64_REL24_NOTOC ? (Thunk *)make<PPC64PCRelPLTStub>(s)
                                        : (Thunk *)make<PPC64PltCallStub>(s);
 
   // This check looks at the st_other bits of the callee. If the value is 1
-  // then the callee clobbers the TOC and we need an R2 save stub.
-  if ((s.stOther >> 5) == 1)
+  // then the callee clobbers the TOC and we need an R2 save stub when RelType
+  // is R_PPC64_REL14 or R_PPC64_REL24.
+  if ((type == R_PPC64_REL14 || type == R_PPC64_REL24) && (s.stOther >> 5) == 1)
     return make<PPC64R2SaveStub>(s);
 
   if (type == R_PPC64_REL24_NOTOC && (s.stOther >> 5) > 1)
     return make<PPC64R12SetupStub>(s);
 
   if (config->picThunk)
-    return make<PPC64PILongBranchThunk>(s, a);
-
-  return make<PPC64PDLongBranchThunk>(s, a);
+    return type == R_PPC64_REL24_NOTOC
+               ? (Thunk *)make<PPC64PCRelPILongBranchThunk>(s, a)
+               : (Thunk *)make<PPC64PILongBranchThunk>(s, a);
+
+  return type == R_PPC64_REL24_NOTOC
+             ? (Thunk *)make<PPC64PCRelPDLongBranchThunk>(s, a)
+             : (Thunk *)make<PPC64PDLongBranchThunk>(s, a);
 }
 
 Thunk *elf::addThunk(const InputSection &isec, Relocation &rel) {
   Symbol &s = *rel.sym;
   int64_t a = rel.addend;
 
   if (config->emachine == EM_AARCH64)
     return addThunkAArch64(rel.type, s, a);

lld/test/ELF/ppc64-pcrel-long-branch-error.s

+# REQUIRES: ppc
+# RUN: echo 'SECTIONS { \
+# RUN:       .text_low 0x2000: { *(.text_low) } \
+# RUN:       .text_high 0x800002000 : { *(.text_high) } \
+# RUN:       }' > %t.script
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64le %s -o %t.o
+# RUN: not ld.lld -T %t.script %t.o -o %t 2>&1 >/dev/null | FileCheck %s
+# RUN: not ld.lld -pie -T %t.script %t.o -o %t 2>&1 >/dev/null | FileCheck %s
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64 %s -o %t.o
+# RUN: not ld.lld -T %t.script %t.o -o %t 2>&1 >/dev/null | FileCheck %s
+# RUN: not ld.lld -pie -T %t.script %t.o -o %t 2>&1 >/dev/null | FileCheck %s
+
+# CHECK: error: offset overflow 34 bits, use large code model with mcmodel=large
+
+.section .text_low, "ax", %progbits
+.globl _start
+_start:
+  bl high@notoc
+  blr
+
+.section .text_high, "ax", %progbits
+.globl high
+high:
+  blr

lld/test/ELF/ppc64-pcrel-long-branch-pi.s

+# REQUIRES: ppc
+# RUN: echo 'SECTIONS { \
+# RUN:       .text_low 0x2000: { *(.text_low) } \
+# RUN:       .text_high 0x2002000 : { *(.text_high) } \
+# RUN:       }' > %t.script
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64le %s -o %t.o
+# RUN: ld.lld -pie -T %t.script %t.o -o %t
+# RUN: llvm-readelf -S %t | FileCheck --check-prefix=SEC-PIE %s
+# RUN: llvm-readobj -r %t | FileCheck --check-prefix=RELOC-PIE %s
+# RUN: llvm-objdump -d --no-show-raw-insn --mcpu=pwr10 %t | FileCheck --check-prefix=CHECK-PIE %s
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64le -defsym HIDDEN=1 %s -o %t.o
+# RUN: ld.lld -shared -T %t.script %t.o -o %t.so
+# RUN: llvm-readelf -S %t.so | FileCheck --check-prefix=SEC-SHARED %s
+# RUN: llvm-readobj -r %t.so | FileCheck --check-prefix=RELOC-SHARED %s
+# RUN: llvm-objdump -d --no-show-raw-insn --mcpu=pwr10 %t.so | FileCheck --check-prefix=CHECK-SHARED %s
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64 %s -o %t.o
+# RUN: ld.lld -pie -T %t.script %t.o -o %t
+# RUN: llvm-readelf -S %t | FileCheck --check-prefix=SEC-PIE %s
+# RUN: llvm-readobj -r %t | FileCheck --check-prefix=RELOC-PIE %s
+# RUN: llvm-objdump -d --no-show-raw-insn --mcpu=pwr10 %t | FileCheck --check-prefix=CHECK-PIE %s
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64 -defsym HIDDEN=1 %s -o %t.o
+# RUN: ld.lld -shared -T %t.script %t.o -o %t.so
+# RUN: llvm-readelf -S %t.so | FileCheck --check-prefix=SEC-SHARED %s
+# RUN: llvm-readobj -r %t.so | FileCheck --check-prefix=RELOC-SHARED %s
+# RUN: llvm-objdump -d --no-show-raw-insn --mcpu=pwr10 %t.so | FileCheck --check-prefix=CHECK-SHARED %s
+
+
+# SEC-PIE: Name       Type     Address          Off     Size   ES Flg Lk Inf Al
+# SEC-PIE: .got       PROGBITS 00000000020020d8 20120d8 000008 00  WA  0   0  8
+# SEC-PIE: .branch_lt NOBITS   00000000020020e8 20120e8 000008 00  WA  0   0  8
+
+# SEC-SHARED: Name       Type     Address          Off     Size   ES Flg Lk Inf Al
+# SEC-SHARED: .got       PROGBITS 00000000020020b8 20120b8 000008 00  WA  0   0  8
+# SEC-SHARED: .branch_lt NOBITS   00000000020020c8 20120c8 000008 00  WA  0   0  8
+
+# RELOC-PIE:      .rela.dyn {
+# RELOC-PIE-NEXT:   0x20020E0 R_PPC64_RELATIVE - 0x8000
+# RELOC-PIE-NEXT:   0x20020E8 R_PPC64_RELATIVE - 0x2002000
+# RELOC-PIE-NEXT: }
+
+# RELOC-SHARED:      .rela.dyn {
+# RELOC-SHARED-NEXT:   0x20020C0 R_PPC64_RELATIVE - 0x8000
+# RELOC-SHARED-NEXT:   0x20020C8 R_PPC64_RELATIVE - 0x2002000
+# RELOC-SHARED-NEXT: }
+
+# CHECK-PIE-LABEL: <_start>:
+# CHECK-PIE-NEXT:    2000: bl 0x2010
+# CHECK-PIE-NEXT:          blr
+# CHECK-PIE-NEXT:          trap
+# CHECK-PIE-NEXT:          trap
+
+## &.branch_lt[0] - 0x2010 = 0x20020E8 - 0x2010 = 33554648
+# CHECK-PIE-LABEL: <__long_branch_pcrel_high>:
+# CHECK-PIE-NEXT:    2010: pld 12, 33554648(0), 1
+# CHECK-PIE-NEXT:          mtctr 12
+# CHECK-PIE-NEXT:          bctr
+
+# CHECK-PIE-LABEL: <high>:
+# CHECK-PIE-NEXT:    2002000: blr
+
+# CHECK-SHARED-LABEL: <_start>:
+# CHECK-SHARED-NEXT:    2000: bl 0x2010
+# CHECK-SHARED-NEXT:          blr
+# CHECK-SHARED-NEXT:          trap
+# CHECK-SHARED-NEXT:          trap
+
+## &.branch_lt[0] - 0x2010 = 0x20020C8 - 0x2010 = 33554616
+# CHECK-SHARED-LABEL: <__long_branch_pcrel_high>:
+# CHECK-SHARED-NEXT:    2010: pld 12, 33554616(0), 1
+# CHECK-SHARED-NEXT:          mtctr 12
+# CHECK-SHARED-NEXT:          bctr
+
+# CHECK-SHARED-LABEL: <high>:
+# CHECK-SHARED-NEXT:    2002000: blr
+
+.section .text_low, "ax", %progbits
+.globl _start
+_start:
+  bl high@notoc
+  blr
+
+.section .text_high, "ax", %progbits
+.ifdef HIDDEN
+.hidden high
+.endif
+.globl high
+high:
+  blr
+
+## Force creation of .got
+## The R_PPC64_RELATIVE makes sure .rela.dyn survives removeUnusedSyntheticSections.
+.section .data
+.quad .TOC.@tocbase

lld/test/ELF/ppc64-pcrel-long-branch.s

+# REQUIRES: ppc
+# RUN: echo 'SECTIONS { \
+# RUN:       .text_low 0x2000: { *(.text_low) } \
+# RUN:       .text_high 0x2002000 : { *(.text_high) } \
+# RUN:       }' > %t.script
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64le %s -o %t.o
+# RUN: ld.lld -T %t.script %t.o -o %t
+# RUN: llvm-readelf -S -r %t | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .branch_lt %t | FileCheck --check-prefix=BRANCH-LE %s
+# RUN: llvm-objdump -d --no-show-raw-insn --mcpu=pwr10 %t | FileCheck %s
+# RUN: llvm-nm --no-sort %t | FileCheck --check-prefix=NM %s
+
+# RUN: llvm-mc -filetype=obj -triple=ppc64 %s -o %t.o
+# RUN: ld.lld -T %t.script %t.o -o %t
+# RUN: llvm-readelf -S -r %t | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .branch_lt %t | FileCheck --check-prefix=BRANCH-BE %s
+# RUN: llvm-objdump -d --no-show-raw-insn --mcpu=pwr10 %t | FileCheck %s
+# RUN: llvm-nm --no-sort %t | FileCheck --check-prefix=NM %s
+
+# SEC: Name       Type     Address          Off     Size   ES Flg Lk Inf Al
+# SEC: .branch_lt PROGBITS 0000000002002008 2002008 000008 00  WA  0   0  8
+# SEC: There are no relocations in this file.
+
+# BRANCH-LE:      Hex dump of section '.branch_lt':
+# BRANCH-LE-NEXT: 0x02002008 00200002 00000000 . ......
+
+# BRANCH-BE:      Hex dump of section '.branch_lt':
+# BRANCH-BE-NEXT: 0x02002008 00000000 02002000 ...... .
+
+# CHECK-LABEL: <_start>:
+# CHECK-NEXT:    2000: bl 0x2010
+# CHECK-NEXT:          blr
+# CHECK-NEXT:          trap
+# CHECK-NEXT:          trap
+
+## &.branch_lt[0] - 0x2010 = 0x2002008 - 0x2010 = 33554424
+# CHECK-LABEL: <__long_branch_pcrel_high>:
+# CHECK-NEXT:    2010: pld 12, 33554424(0), 1
+# CHECK-NEXT:          mtctr 12
+# CHECK-NEXT:          bctr
+
+# CHECK-LABEL: <high>:
+# CHECK-NEXT:    2002000: blr
+
+.section .text_low, "ax", %progbits
+.globl _start
+_start:
+  bl high@notoc
+  blr
+
+.section .text_high, "ax", %progbits
+.globl high
+high:
+  blr
+
+# NM:      0000000000002010 t __long_branch_pcrel_high
+# NM-NEXT: 0000000000002000 T _start
+# NM-NEXT: 0000000002002000 T high