[LLD][ELF] Pre-create ThunkSections at Target specific intervals

[peter.smith]

Summary

When an OutputSection is larger than the branch range for a Target we need to place thunks such that they are always in range of their caller, and sufficiently spaced to maximise the number of callers that can use the thunk. For ARMv7a we use the simple heuristic of placing the ThunkSection at intervals corresponding to the Thumb2 branch range. If the OutputSection is small we put the thunks at the end of the executable sections.

There are many alternative strategies for Thunk placement to maximize reuse. I've gone for a simple implementation that places the majority of Thunks slightly less than the most common branch range into the OutputSection. I think that this will work well in the most common case, a single .text OutputSection.

[peter.smith]

Rebased to account for changes in D31654

[peter.smith]

I'm abandoning the range thunks implementation that inserts into OutputSections in favour of an implementation that inserts into InputSectionDescription.

ELF/Relocations.h

 class Thunk;
 template <class ELFT> class ThunkCreator {
 public:
   // Return true if Thunks have been added to OutputSections
   bool createThunks(ArrayRef<OutputSection *> OutputSections);
 
 private:
   void mergeThunks();
-  ThunkSection *getOSThunkSec(ThunkSection *&TS, OutputSection *OS);
+  void createInitialThunkSections(ArrayRef<OutputSection *> OutputSections);
+  ThunkSection *getOSThunkSec(OutputSection *OS, InputSection *IS);
   ThunkSection *getISThunkSec(InputSection *IS, OutputSection *OS);
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, uint32_t Type);
   ThunkSection *addThunkSection(OutputSection *OS, uint64_t Off);
 
   uint32_t Pass = 0;
   // Record all the available Thunks for a Symbol
   llvm::DenseMap<SymbolBody *, std::vector<Thunk *>> ThunkedSymbols;
   // Find a Thunk from the Thunks symbol definition, we can use this to find

ELF/Relocations.cpp

 // in the Sections vector, and recalculate the InputSection output section
 // offsets.
 // This may invalidate any output section offsets stored outside of InputSection
 template <class ELFT> void ThunkCreator<ELFT>::mergeThunks() {
   for (auto &KV : NewThunkSections) {
     OutputSection *OS = KV.first;
     std::vector<ThunkSection *> &Thunks = KV.second;
 
+    // Remove ThunkSections with no Thunks
+    auto ThunkBegin = Thunks.begin();
+    auto ThunkEnd = Thunks.end();
+    ThunkEnd = std::remove_if(ThunkBegin, ThunkEnd, [](const ThunkSection *TS) {
+      return TS->getSize() == 0;
+    });
+    if (ThunkBegin == ThunkEnd)
+      continue;
+
     // Order Thunks in ascending OutSecOff
     auto ThunkCmp = [](const ThunkSection *A, const ThunkSection *B) {
       return A->OutSecOff < B->OutSecOff;
     };
-    std::stable_sort(Thunks.begin(), Thunks.end(), ThunkCmp);
+    std::stable_sort(ThunkBegin, ThunkEnd, ThunkCmp);
 
     // Merge sorted vectors of Thunks and InputSections by OutSecOff
     std::vector<InputSection *> Tmp;
-    Tmp.reserve(OS->Sections.size() + Thunks.size());
+    Tmp.reserve(OS->Sections.size() + std::distance(ThunkBegin, ThunkEnd));
     auto MergeCmp = [](const InputSection *A, const InputSection *B) {
       // std::merge requires a strict weak ordering.
       if (A->OutSecOff < B->OutSecOff)
         return true;
       if (A->OutSecOff == B->OutSecOff)
         // Check if Thunk is immediately before any specific Target InputSection
         // for example Mips LA25 Thunks.
         if (auto *TA = dyn_cast<ThunkSection>(A))
           if (TA && TA->getTargetInputSection() == B)
             return true;
       return false;
     };
-    std::merge(OS->Sections.begin(), OS->Sections.end(), Thunks.begin(),
-               Thunks.end(), std::back_inserter(Tmp), MergeCmp);
+    std::merge(OS->Sections.begin(), OS->Sections.end(), ThunkBegin, ThunkEnd,
+               std::back_inserter(Tmp), MergeCmp);
     OS->Sections = std::move(Tmp);
 
     // We need to insert the sections into the linker script input section
     // commands for the correct output order
     if (Script->Opt.HasSections)
       Script->syncWithOS(OS);
   }
 }
 
+// Create one or more ThunkSections per OS that can be used to place
+// non-inline Thunks. We attempt to place the ThunkSections using the following
+// desirable properties:
+// - Within range of the maximum number of callers
+// - Minimise number of ThunkSections that need inserting
+//
+// We follow a simple but conservative heuristic to place ThunkSections close
+// to a Target specific branch range. For an OutputSection that is smaller than
+// the range then a single ThunkSection at the end will do.
 template <class ELFT>
-ThunkSection *ThunkCreator<ELFT>::getOSThunkSec(ThunkSection *&TS,
-                                                OutputSection *OS) {
-  if (TS == nullptr) {
+void elf::ThunkCreator<ELFT>::createInitialThunkSections(
+    ArrayRef<OutputSection *> OutputSections) {
+
+  bool NeedTrailingTS = true;
+  for (OutputSection *Base : OutputSections) {
+    auto *OS = dyn_cast<OutputSection>(Base);
+    if (OS == nullptr)
+      continue;
     uint32_t Off = 0;
+    uint32_t Limit = Target->ThunkSectionSpacing - Target->ThunkSectionSize;
+    InputSection *PrevIS = nullptr;
     for (auto *IS : OS->Sections) {
       Off = IS->OutSecOff + IS->getSize();
+      if (Off >= Limit) {
+        uint32_t ThunkOff = PrevIS->OutSecOff + PrevIS->getSize();
+        addThunkSection(OS, ThunkOff);
+        NeedTrailingTS = false;
+        Limit = ThunkOff + Target->ThunkSectionSpacing;
+      }
       if ((IS->Flags & SHF_EXECINSTR) == 0)
         break;
-    }
-    TS = addThunkSection(OS, Off);
-  }
+      PrevIS = IS;
+    }
+    if (NeedTrailingTS)
+      addThunkSection(OS, Off);
+
+template <class ELFT>
+ThunkSection *ThunkCreator<ELFT>::getOSThunkSec(OutputSection *OS,
+                                                InputSection *IS) {
+  // Until range extension thunks just return the first section
+  for (ThunkSection *TS : ThunkSections[OS]) {
     return TS;
   }
+  // No suitable ThunkSection exists.
+  return addThunkSection(OS, IS->OutSecOff);
+}
 
 template <class ELFT>
 ThunkSection *ThunkCreator<ELFT>::getISThunkSec(InputSection *IS,
                                                 OutputSection *OS) {
   ThunkSection *TS = ThunkedSections.lookup(IS);
   if (TS)
     return TS;
   auto *TOS = cast<OutputSection>(IS->OutSec);
bool ThunkCreator<ELFT>::createThunks(
     ArrayRef<OutputSection *> OutputSections) {
   bool AddressesChanged = false;
   if (Pass > 0) {
     NewThunkSections.clear();
     if (Pass == 2)
       // With existing Thunks pass 0 will create Thunks, pass 1 will
       // create no more Thunks so if we get to 2 something has gone wrong.
       fatal("Thunk creation not converged in sufficient number of passes");
+  } else if (Target->ThunkSectionSpacing) {
+    createInitialThunkSections(OutputSections);
   }
 
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into the OutputSection.
 
   // We separate the creation of ThunkSections from the insertion of the
   // ThunkSections back into the OutputSection as ThunkSections are not always
   // inserted into the same OutputSection as the caller.
   for (OutputSection *OS : OutputSections) {
-    ThunkSection *OSTS = nullptr;
     for (InputSection *IS : OS->Sections) {
       if (dyn_cast<ThunkSection>(IS) != nullptr)
         // Do not create Thunks for relocations from Thunks
         continue;
       for (Relocation &Rel : IS->Relocations) {
         SymbolBody &Body = *Rel.Sym;
         // If this Relocation is using a Thunk, use it.
         if (Thunks.find(&Body) != Thunks.end())
           continue;
         if (Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body)) {
           Thunk *T;
           bool IsNew;
           std::tie(T, IsNew) = getThunk(Body, Rel.Type);
           if (IsNew) {
             AddressesChanged = true;
             // Find or create a ThunkSection for the new Thunk
             ThunkSection *TS;
             if (auto *TIS = T->getTargetInputSection())
               TS = getISThunkSec(TIS, OS);
             else
-              TS = getOSThunkSec(OSTS, OS);
+              TS = getOSThunkSec(OS, IS);
             TS->addThunk(T);
             Thunks[T->ThunkSym] = T;
           }
           // Redirect relocation to Thunk, we never go via the PLT to a Thunk
           Rel.Sym = T->ThunkSym;
           Rel.Expr = fromPlt(Rel.Expr);
         }
       }

ELF/Target.h

public:
   unsigned DefaultMaxPageSize = 4096;
 
   // On FreeBSD x86_64 the first page cannot be mmaped.
   // On Linux that is controled by vm.mmap_min_addr. At least on some x86_64
   // installs that is 65536, so the first 15 pages cannot be used.
   // Given that, the smallest value that can be used in here is 0x10000.
   uint64_t DefaultImageBase = 0x10000;
 
+  // On systems with range extensions we place collections of Thunks at
+  // regular spacings that enable the majority of branches reach the Thunks.
+  uint32_t ThunkSectionSpacing = 0x0;
+  // An estimate of how many thunks will be needed in a given
+  // ThunkSectionSpacing
+  uint32_t ThunkSectionSize = 0x0;
+
   uint32_t CopyRel;
   uint32_t GotRel;
   uint32_t PltRel;
   uint32_t RelativeRel;
   uint32_t IRelativeRel;
   uint32_t TlsDescRel;
   uint32_t TlsGotRel;
   uint32_t TlsModuleIndexRel;