[ELF] Optimize getISDThunkSec() to amortized O(1) in thunk creation

[MaskRay]

Summary

The time complexity of getISDThunkSec() is O(|ISD->ThunkSections|).
When thunk section spacing is enabled, ISD->ThunkSections can be in the
scale of size(ISD)/getThunkSectionSpacing(). In one large powerpc64le
executable, this number for .text is 25980.

It is very slow if every created thunk in the current
InputSectionDescription goes through the whole array.

Sort relocations by offset and leverage this property to optimize it to O(1):

If a thunk is located before the current relocation offset, once it
can't be reached, any subsequent relocation can't reach this thunk,
either.

[peter.smith]

If I understand correctly I think this could prematurely skip over ThunkSections if there is more than one branch relocation range. For example consider a case where there are two relocation ranges S (short) and L (long). If we search for a ThunkSection for S where the ThunkSection spacing is L then there is a chance that at a relocation with range S at offset O will be out of range of one of more ThunkSections, but these would have been in range had it been R. The next relocation with range L at offset O2 will not even check some ThunkSections that it would have been in range of. The chances of this happening are much greater when S is much smaller than L.

Short-branch-needing-thunk
Long-branch-needing-thunk
...
ThunkSection out of range of short-branch, but in range of long
...

I may be missing something though? If I'm right I think that you would need to store a ThunkSecIdx per relocation range for this to give the same results as the existing code. Another possibility is that ThunkSecIdx is only written back to for the largest relocation range.

[MaskRay]

if there is more than one branch relocation range.

Good point - there can be more than one branch types. I didn't know the code well when I created this patch.

If I choose 0x2000000 for ppc64le thunk section spacing (I tried several number slightly smaller than 0x2000000; they have no differences), ThunkSections.size() is at most 22. I'll abandon this.

ELF/Relocations.h

public:
   // number of times it can be called to prevent infinite loops.
   uint32_t Pass = 0;
 
 private:
   void mergeThunks(ArrayRef<OutputSection *> OutputSections);
 
   ThunkSection *getISDThunkSec(OutputSection *OS, InputSection *IS,
                                InputSectionDescription *ISD, uint32_t Type,
-                               uint64_t Src);
+                               uint64_t Src, unsigned &ThunkSecIdx);
 
   ThunkSection *getISThunkSec(InputSection *IS);
 
   void createInitialThunkSections(ArrayRef<OutputSection *> OutputSections);
 
   std::pair<Thunk *, bool> getThunk(Symbol &Sym, RelType Type, uint64_t Src);
 
   ThunkSection *addThunkSection(OutputSection *OS, InputSectionDescription *,

ELF/Relocations.cpp

static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
   OffsetGetter GetOffset(Sec);
 
   // Not all relocations end up in Sec.Relocations, but a lot do.
   Sec.Relocations.reserve(Rels.size());
 
   for (auto I = Rels.begin(), End = Rels.end(); I != End;)
     scanReloc<ELFT>(Sec, GetOffset, I, End);
 
-  // Sort relocations by offset for more efficient searching for
-  // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64.
-  if (Config->EMachine == EM_RISCV ||
-      (Config->EMachine == EM_PPC64 && Sec.Name == ".toc"))
+  // Efficient searching for R_RISCV_PCREL_HI20 and R_PPC64_ADDR64, and targets
+  // need thunks require relocations sorted by offset.
+  if (Target->NeedsThunks || Config->EMachine == EM_RISCV)
     llvm::stable_sort(Sec.Relocations,
                       [](const Relocation &LHS, const Relocation &RHS) {
                         return LHS.Offset < RHS.Offset;
                       });
 }
 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
   if (S.AreRelocsRela)
forEachInputSectionDescription(
       });
 }
 
 // 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.* }.
 ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *OS, InputSection *IS,
                                            InputSectionDescription *ISD,
-                                           uint32_t Type, uint64_t Src) {
-  for (std::pair<ThunkSection *, uint32_t> TP : ISD->ThunkSections) {
-    ThunkSection *TS = TP.first;
+                                           uint32_t Type, uint64_t Src,
+                                           unsigned &ThunkSecIdx) {
+  for (unsigned E = ISD->ThunkSections.size(); ThunkSecIdx != E;
+       ++ThunkSecIdx) {
+    ThunkSection *TS = ISD->ThunkSections[ThunkSecIdx].first;
     uint64_t TSBase = OS->Addr + TS->OutSecOff;
     uint64_t TSLimit = TSBase + TS->getSize();
     if (Target->inBranchRange(Type, Src, (Src > TSLimit) ? TSBase : TSLimit))
       return TS;
+    if (Src < TSLimit)
+      break;
+
+    // If we reach here, we know ThunkSecIdx cannot satisfy any subsequent
+    // relocation, which has a larger offset. Thus we skip it (++ThunkSecIdx).
   }
 
   // No suitable ThunkSection exists. This can happen when there is a branch
   // with lower range than the ThunkSection spacing or when there are too
   // many Thunks. Create a new ThunkSection as close to the InputSection as
   // possible. Error if InputSection is so large we cannot place ThunkSection
   // anywhere in Range.
   uint64_t ThunkSecOff = IS->OutSecOff;
bool ThunkCreator::createThunks(ArrayRef<OutputSection *> OutputSections) {
 
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into InputSectionDescriptions.
   // We separate the creation of ThunkSections from the insertion of the
   // ThunkSections as ThunkSections are not always inserted into the same
   // InputSectionDescription as the caller.
   forEachInputSectionDescription(
       OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
+        unsigned ThunkSecIdx = 0;
         for (InputSection *IS : ISD->Sections)
           for (Relocation &Rel : IS->Relocations) {
             uint64_t Src = IS->getVA(Rel.Offset);
 
             // If we are a relocation to an existing Thunk, check if it is
             // still in range. If not then Rel will be altered to point to its
             // original target so another Thunk can be generated.
             if (Pass > 0 && normalizeExistingThunk(Rel, Src))
               continue;
 
             if (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Src,
                                     *Rel.Sym))
               continue;
 
             Thunk *T;
             bool IsNew;
             std::tie(T, IsNew) = getThunk(*Rel.Sym, Rel.Type, Src);
 
             if (IsNew) {
               // 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);
+                TS = getISDThunkSec(OS, IS, ISD, Rel.Type, Src, ThunkSecIdx);
               TS->addThunk(T);
               Thunks[T->getThunkTargetSym()] = T;
             }
 
             // Redirect relocation to Thunk, we never go via the PLT to a Thunk
             Rel.Sym = T->getThunkTargetSym();
             Rel.Expr = fromPlt(Rel.Expr);
           }