[PPC64] implement Thunk Section Spacing

[adalava]

Summary

This implements PPC64 Thunk Section Spacing to be in PPC64_REL14 range suggestion by sfertile while discussing [1] corruption of ".init" section seen during tests building FreeBSD for PowerPC64-ELFv2 ABI.

[1] https://bugs.llvm.org/show_bug.cgi?id=40740

[ruiu]

lld/ELF/Arch/PPC64.cpp

1056

Could you extend the comment a bit to make it a complete sentence explaining what this value means. I'd say we create initial thunks at regular spacing so that most relocations reach the thunks. On PPC64, REL14 (whose offset is 0x8000) is the most strict relocation.

[MaskRay]

@atanasyan Should MIPS override getThunkSectionSpacing as well? Then we can make the function pure virtual: virtual uint32_t getThunkSectionSpacing() const = 0;

lld/ELF/Arch/PPC64.cpp

1057

This probably should be slightly smaller than 0x8000.

@peter.smith probably has idea how the ARM/AArch64 constants were derived.

uint32_t AArch64::getThunkSectionSpacing() const {
  // See comment in Arch/ARM.cpp for a more detailed explanation of
  // getThunkSectionSpacing(). For AArch64 the only branches we are permitted to
  // Thunk have a range of +/- 128 MiB
  return (128 * 1024 * 1024) - 0x30000;
}

lld/test/ELF/ppc64-branch-thunkspacing.s

4

-o %t.o

6

No 2>&1. It is only used to check warnings/errors.

7

You can omit -triple=powerpc64-unknown-freebsd13.0. llvm-objdump auto detects the triple.

19

mixed tab and spaces? Probably move the bl instruction to another .init section:

.section .init,"ax",@progbits,unique,2
.align 2
  bl too_far1

to mimic the crti.o crtn.o .init

[sfertile]

Thanks for posting this @adalava.

lld/ELF/Arch/PPC64.cpp

1057

The conditional branch instructions only encode a 14-bit immediate which gets shifted left 2 places to form a 4-byte aligned signed 16-bit offset. This gives us a range of [0x8000, 0x7ffc]. Since we have slightly less 'reach' with positive offsets we should start with a spacing of 0x7ffc instead of 0x8000. Then I guess we want to make it slightly smaller so that a branch can reach more then just the first/last instruction in the thunk section.

[peter.smith]

In D61610#1492927, @MaskRay wrote:

@atanasyan Should MIPS override getThunkSectionSpacing as well? Then we can make the function pure virtual: virtual uint32_t getThunkSectionSpacing() const = 0;

I believe the Mips LA25 Thunks are not range extension thunks, they are PI to non-PI and they are a special case where they have to precede their Target Section. We do this with getTargetInputSection() so I think it doesn't matter for Mips.

lld/ELF/Arch/PPC64.cpp

1057

Sorry for the delay in responding. The ThunkSectionSpacing is derived from the branch range - a slop-space (0x30000) bytes to account for the space of thunks that could be generated in between the branch and destination. This is quite pessimistic but given the range is 128 Megabytes, this isn't much of a problem. What I suggest is to think how many Thunks would get created in any [0x8000, 0x7ffc] span and then subtract the size in bytes from that.

It is worth noting that in terms of range, the implementation should fail safe, i.e. it will place any Thunk that can't read one of the pre-created ThunkSections prior in a newly created ThunkSection either before or after the Target.

I note that this caused a problem as there were two InputSections that should not be split by inserting a Thunk in between them. I think the only fool proof solution to that is to make the Thunk implementation aware of the restriction. Arm's proprietary linker has "inline thunks" for v4t that have control flow that falls-through into the following section, in that linker we had to make sure that no thunk got inserted in between the "inline thunk" and the following section.

[adalava]

• add space reservation, add comments and improve test

[adalava]

fix patch

[adalava]

Thank you guys. I updated the patch,;

@sfertile , I posted the patch while you're adding your comment. I guess last version covers your concern, but please give another look.

[MaskRay]

I was trying to find a good value used in
uint32_t PPC64::getThunkSectionSpacing() const { return 0x8000 - 0x1000; } before I noticed this caused an extreme slowdown in thunk creation.

We have a large program whose text segment is of 1.3GiB. Its OutputSection .text consists of 1948775 InputSections. It takes 20 seconds to link but with this patch it doesn't stop in 10 minutes.

The reason is that:

// O(|ThunkVec|). Not the critical path, but there is a bottleneck, too. Many ThunkVec's have hundreds/thousands of elements
            std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src); 

            if (IsNew) { // called 112353 times
              // Find or create a ThunkSection for the new Thunk
              ThunkSection *TS;
              if (auto *TIS = T->getTargetInputSection())
                TS = getISThunkSec(TIS);
              else
                TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src); // it takes O(|ISD->ThunkSections|) time, `ISD->ThunkSections` is large (25980) when getThunkSectionSpacing is enabled.
              TS->addThunk(T);
              Thunks[T->getThunkTargetSym()] = T;
            }

lld/test/ELF/ppc64-branch-thunkspacing.s

19

This comment is not done.

You should create several .init sections to emulate .init used on FreeBSD: it is built from bits spread across several object files.

[peter.smith]

In D61610#1494525, @MaskRay wrote:

I was trying to find a good value used in
uint32_t PPC64::getThunkSectionSpacing() const { return 0x8000 - 0x1000; } before I noticed this caused an extreme slowdown in thunk creation.

We have a large program whose text segment is of 1.3GiB. Its OutputSection .text consists of 1948775 InputSections. It takes 20 seconds to link but with this patch it doesn't stop in 10 minutes.

The reason is that:

// O(|ThunkVec|). Not the critical path, but there is a bottleneck, too. Many ThunkVec's have hundreds/thousands of elements
            std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src); 

            if (IsNew) { // called 112353 times
              // Find or create a ThunkSection for the new Thunk
              ThunkSection *TS;
              if (auto *TIS = T->getTargetInputSection())
                TS = getISThunkSec(TIS);
              else
                TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src); // it takes O(|ISD->ThunkSections|) time, `ISD->ThunkSections` is large (25980) when getThunkSectionSpacing is enabled.
              TS->addThunk(T);
              Thunks[T->getThunkTargetSym()] = T;
            }

Looking at the comment:

//      - b[l,a]  PPC64_REL24 range [33,554,432...33,554,428]
//      - bc[l,a] PPC64_REL14 range [-32,768...32764]
// We take the most strict range and intentionally use a lower
// size than the maximum branch range so the end of the ThunkSection
// is more likely to be within range of the branch instruction that 
// is furthest away.

I strongly recommend taking the longer range (32 Mb) for the ThunkSection spacing. If PPC is anything like Arm, I would be very surprised to see a lot of inter-section conditional branches, and with a range that low the chances of finding a reuse spot within 32k seems extremely low. In Arm we use the longest range, most common Thumb2 branch range of 16Mb to place the Thunk Sections and rely on the tidy up part in // No suitable ThunkSection exists. for the shorter-range 16Mb sections. I think that strategy could be used for PPC and would have roughly 40 ThunkSections in a 1.3Gb text section.

If there are many 32k conditional branches in the program then I think the original strategy of not using the ThunkSectionSpacing is the right way to go, there just won't be enough reuse opportunity to make it worthwhile.

[MaskRay]

In D61610#1494577, @peter.smith wrote:

In D61610#1494525, @MaskRay wrote:

I was trying to find a good value used in
uint32_t PPC64::getThunkSectionSpacing() const { return 0x8000 - 0x1000; } before I noticed this caused an extreme slowdown in thunk creation.

We have a large program whose text segment is of 1.3GiB. Its OutputSection .text consists of 1948775 InputSections. It takes 20 seconds to link but with this patch it doesn't stop in 10 minutes.

The reason is that:

// O(|ThunkVec|). Not the critical path, but there is a bottleneck, too. Many ThunkVec's have hundreds/thousands of elements
            std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src); 

            if (IsNew) { // called 112353 times
              // Find or create a ThunkSection for the new Thunk
              ThunkSection *TS;
              if (auto *TIS = T->getTargetInputSection())
                TS = getISThunkSec(TIS);
              else
                TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src); // it takes O(|ISD->ThunkSections|) time, `ISD->ThunkSections` is large (25980) when getThunkSectionSpacing is enabled.
              TS->addThunk(T);
              Thunks[T->getThunkTargetSym()] = T;
            }

Looking at the comment:

//      - b[l,a]  PPC64_REL24 range [33,554,432...33,554,428]
//      - bc[l,a] PPC64_REL14 range [-32,768...32764]
// We take the most strict range and intentionally use a lower
// size than the maximum branch range so the end of the ThunkSection
// is more likely to be within range of the branch instruction that 
// is furthest away.

I strongly recommend taking the longer range (32 Mb) for the ThunkSection spacing. If PPC is anything like Arm, I would be very surprised to see a lot of inter-section conditional branches, and with a range that low the chances of finding a reuse spot within 32k seems extremely low. In Arm we use the longest range, most common Thumb2 branch range of 16Mb to place the Thunk Sections and rely on the tidy up part in // No suitable ThunkSection exists. for the shorter-range 16Mb sections. I think that strategy could be used for PPC and would have roughly 40 ThunkSections in a 1.3Gb text section.

If there are many 32k conditional branches in the program then I think the original strategy of not using the ThunkSectionSpacing is the right way to go, there just won't be enough reuse opportunity to make it worthwhile.

I just wanted to make the same comment :) I think 0x8000 is too small. One of the bottlenecks is D61666, but it doesn't fix the problem.

The second bottleneck is at:

for (Thunk *T : *ThunkVec)
  if (T->isCompatibleWith(Type) && ////// many R_PPC64_REL24 branches can't be satisfied by the initially created thunks 
      Target->inBranchRange(Type, Src, T->getThunkTargetSym()->getVA()))
    return std::make_pair(T, false);

uint32_t PPC64::getThunkSectionSpacing() const {
  return 0x2000000; // good choice, but it should be decreased a bit
}

Then, I think D61629 is still useful. I'll revive it.

[sfertile]

In D61610#1494577, @peter.smith wrote:

If PPC is anything like Arm, I would be very surprised to see a lot of inter-section conditional branches,

Yeah, in my experience theses are rare compared to the normal unconditional branch.

In D61610#1494589, @MaskRay wrote:

uint32_t PPC64::getThunkSectionSpacing() const {
  return 0x2000000; // good choice, but it should be decreased a bit
}

Since thunks sections will still get added closer if the pre-allocated ones can't satisfy a branch, and the number of pre-allocated sections drastically affects our link time maybe go with this (or maybe even slightly larger?).

In D61610#1494525, @MaskRay wrote:

We have a large program whose text segment is of 1.3GiB. Its OutputSection .text consists of 1948775 InputSections. It takes 20 seconds to link but with this patch it doesn't stop in 10 minutes.

I think you are in a unique situation where you have some *really good* test input for investigating how pre-allocating the thunks affects link time, do any of these larger programs have open-source equivalents? Most of the stuff I used for testing the thunk creation was either shared libraries or executable based on llvm/clang (for long-branch thunks). I would expect the shared libraries to use most of the thunk sections we create, but would love to be able to look at some larger executables to see how often the sections are used there. We might be better off not setting this value on PPC like Peter suggests.

lld/test/ELF/ppc64-branch-thunkspacing.s

19

Should we have a simple test simply checking the thunk section spacing for this patch and then have a follow on patch where we fix the thunk insertion to not insert into the middle of .init and .fini sections and test the multiple .init sections there?

[adalava]

increase to PPC64_REL24 range

[adalava]

update testcase to use readelf instead of objdump, so it doesn't depend on D61647 anymore

[adalava]

lld/test/ELF/ppc64-branch-thunkspacing.s

19

Sure. I'm not sure on how to check that spacing was applied. I know empirically the offsets are different, so I did this test.
Any guidance on how to improve this test is welcome.

[MaskRay]

@adalava We care about the link time. I need to do some testing to ensure this doesn't cause regression. I've created https://reviews.llvm.org/D61720, fixed the tests and added ppc64-long-branch-init.s that I think captures the idea of the fix. Hope you don't mind my commandeering the change :)

lld/test/ELF/ppc64-branch-thunkspacing.s

19

I think you can extract the .init section of crti.o crtbegin.o crtend.o crtn.o, and so something like:

.section .init,"ax",@progbits,unique,1
...

.section .init,"ax",@progbits,unique,2
...

.section .init,"ax",@progbits,unique,3
...

.section .init,"ax",@progbits,unique,4
...

[adalava]

In D61610#1496129, @MaskRay wrote:

@adalava We care about the link time. I need to do some testing to ensure this doesn't cause regression. I've created https://reviews.llvm.org/D61720, fixed the tests and added ppc64-long-branch-init.s that I think captures the idea of the fix. Hope you don't mind my commandeering the change :)

Np MaskRay, thank you for improving the patch. Abandoning this review in favor of D61720.

lld/ELF/Arch/PPC64.cpp

public:
   void relaxGot(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsGdToIe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsGdToLe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsLdToLe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsIeToLe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
 
   bool adjustPrologueForCrossSplitStack(uint8_t *Loc, uint8_t *End,
                                         uint8_t StOther) const override;
+  uint32_t getThunkSectionSpacing() const override;
 };
 } // namespace
 
 // Relocation masks following the #lo(value), #hi(value), #ha(value),
 // #higher(value), #highera(value), #highest(value), and #highesta(value)
 // macros defined in section 4.5.1. Relocation Types of the PPC-elf64abi
 // document.
 static uint16_t lo(uint64_t V) { return V; }
if (HiImm) {
     // addi r12, r1, imm
     write32(Loc + 4, (0x39810000) | (uint16_t)LoImm);
     write32(Loc + 8, 0x60000000);
   }
 
   return true;
 }
 
+uint32_t PPC64::getThunkSectionSpacing() const {
+  // PowerPC64 has the following basic branch instructions:
+  //
+  //      - b[l,a]  PPC64_REL24 range [33,554,432...33,554,428]
+  //      - bc[l,a] PPC64_REL14 range [-32,768...32764]
+  //
+  // We take the less strict range, and intentionally use a lower
+  // size than the maximum branch range so the end of the ThunkSection
+  // is more likely to be within range of the branch instruction that
+  // is furthest away.
+  //
+  // Reducing it in 0x80000 allow creating 32,768 16 byte Thunks at any
+  // offset in a ThunkSection without risk of a branch to one of the
+  // Thunks going out of range.
+  //
+  // See comment in Arch/ARM.cpp for more detais of getThunkSectionSpacing().
+  return 0x2000000 - 0x80000;
+}
+
 TargetInfo *elf::getPPC64TargetInfo() {
   static PPC64 Target;
   return &Target;
 }

lld/test/ELF/Inputs/ppc64-far-branch-rangethunk.s

+
+.section .init,"ax",@progbits,unique,2
+.align 2
+.global too_far1
+.type too_far1,%function
+
+// place too_far1 to + 64MB (should be above 32MB)
+too_far1 = 0x10010000 + 0x4000000
+

lld/test/ELF/ppc64-branch-thunkspacing.s

+# REQUIRES: ppc
+
+# RUN: llvm-mc -filetype=obj -triple=powerpc64-unknown-freebsd13.0 %s -o %t.o
+# RUN: llvm-mc -filetype=obj -triple=powerpc64-unknown-freebsd13.0 %S/Inputs/ppc64-far-branch-rangethunk.s -o %tfar.o
+# RUN: ld.lld  %t.o %tfar.o -o %t2
+# RUN: llvm-readelf --symbols %t2 | FileCheck %s
+
+.section .init,"ax",@progbits
+.align  2
+.globl  _start
+.type   _start,@function
+
+_start:
+  stwu 1,-16(1)
+  mflr 0
+  stw 31,12(1)
+  stw 0,20(1)
+  mr 31,1
+  bl  too_far1
+
+
+# When ThunkSpacing is applied, "__long_branch_too_far1" is shifted
+#   to an offset after "_start"
+
+# CHECK: Symbol table '.symtab' contains 4 entries:
+# CHECK:      0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
+# CHECK-NEXT:      1: 0000000010010018    16 FUNC    LOCAL  DEFAULT    2 __long_branch_too_far1
+# CHECK-NEXT:      2: 0000000010010000     0 FUNC    GLOBAL DEFAULT    2 _start
+# CHECK-NEXT:      3: 0000000014010000     0 FUNC    GLOBAL DEFAULT  ABS too_far1
+