[LLD][ELF] Make createThunks() iterate until no more thunks added

[peter.smith]

Summary

We now continually call createThunks() until no more thunks are added. This requires us to record the thunks we add on each pass and only merge these into the OutputSection. We also need to check if a Relocation is targeting a thunk to prevent us from infinitely creating more thunks.

With the existing thunks we allocate all the thunks on the first pass, the second pass will not result in any more thunks. When range extension thunks are introduced we will need more passes.

[peter.smith]

Rebased patch after earlier changes made to 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(OutputSection *OS, std::vector<ThunkSection *> &Thunks);
+  void mergeThunks();
   ThunkSection *getOSThunkSec(ThunkSection *&TS, OutputSection *OS);
   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;
 
   // Track Symbols that already have a Thunk
   llvm::DenseMap<SymbolBody *, Thunk *> ThunkedSymbols;
 
+  // Find a Thunk from the Thunks symbol definition, we can use this to find
+  // the Thunk from a relocation to the Thunks symbol definition.
+  llvm::DenseMap<SymbolBody *, Thunk *> Thunks;
+
   // Track InputSections that have a ThunkSection placed in front
   llvm::DenseMap<InputSection *, ThunkSection *> ThunkedSections;
 
-  // Track the ThunksSections that need to be inserted into an OutputSection
+  // All the ThunkSections that we have created, organised by OutputSection
+  // will contain a mix of ThunkSections that have been created this pass, and
+  // ThunkSections that have been merged into the OutputSection on previous
+  // passes
   std::map<OutputSection *, std::vector<ThunkSection *>> ThunkSections;
+
+  // All the ThunkSections we have created this pass, organised per
+  // OutputSection. All the ThunkSections in NewThunkSections will be merged
+  // into the OutputSection if they contain any Thunks.
+  std::map<OutputSection *, std::vector<ThunkSection *>> NewThunkSections;
 };
 
 // Return a int64_t to make sure we get the sign extension out of the way as
 // early as possible.
 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rel &Rel) {
   return 0;
 }
 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }
 }
 }
 
 #endif

ELF/Relocations.cpp

template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
   else
     scanRelocs<ELFT>(S, S.rels<ELFT>());
 }
 
 // Insert the Thunks for OutputSection OS into their designated place
 // 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(OutputSection *OS,
-                                     std::vector<ThunkSection *> &Thunks) {
+template <class ELFT> void ThunkCreator<ELFT>::mergeThunks() {
+  for (auto &KV : NewThunkSections) {
+    OutputSection *OS = KV.first;
+    std::vector<ThunkSection *> &Thunks = KV.second;
+
     // 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);
 
     // Merge sorted vectors of Thunks and InputSections by OutSecOff
     std::vector<InputSection *> Tmp;
     Tmp.reserve(OS->Sections.size() + Thunks.size());
     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);
     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);
-  OS->assignOffsets();
+  }
 }
 
 template <class ELFT>
 ThunkSection *ThunkCreator<ELFT>::getOSThunkSec(ThunkSection *&TS,
                                                 OutputSection *OS) {
   if (TS == nullptr) {
     uint32_t Off = 0;
     for (auto *IS : OS->Sections) {
       Off = IS->OutSecOff + IS->getSize();
       if ((IS->Flags & SHF_EXECINSTR) == 0)
         break;
     }
-    TS = make<ThunkSection>(OS, Off);
-    ThunkSections[OS].push_back(TS);
+    TS = addThunkSection(OS, Off);
   }
   return TS;
 }
 
 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);
-  TS = make<ThunkSection>(TOS, IS->OutSecOff);
-  ThunkSections[TOS].push_back(TS);
+  TS = addThunkSection(TOS, IS->OutSecOff);
   ThunkedSections[IS] = TS;
   return TS;
 }
 
 template <class ELFT>
 std::pair<Thunk *, bool> ThunkCreator<ELFT>::getThunk(SymbolBody &Body,
                                                       uint32_t Type) {
   auto res = ThunkedSymbols.insert({&Body, nullptr});
   if (res.second)
     res.first->second = addThunk<ELFT>(Type, Body);
   return std::make_pair(res.first->second, res.second);
 }
 
+// Make a new ThunkSection at offset Off and it to the persistent and per pass
+// records per OutputSection.
+template <class ELFT>
+ThunkSection *ThunkCreator<ELFT>::addThunkSection(OutputSection *OS,
+                                                  uint64_t Off) {
+  auto *TS = make<ThunkSection>(OS, Off);
+  ThunkSections[OS].push_back(TS);
+  NewThunkSections[OS].push_back(TS);
+  return TS;
+}
+
 // Process all relocations from the InputSections that have been assigned
 // to OutputSections and redirect through Thunks if needed.
 //
 // createThunks must be called after scanRelocs has created the Relocations for
 // each InputSection. It must be called before the static symbol table is
 // finalized. If any Thunks are added to an OutputSection the output section
 // offsets of the InputSections will change.
 //
 // FIXME: All Thunks are assumed to be in range of the relocation. Range
 // extension Thunks are not yet supported.
 template <class ELFT>
 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");
+  }
+
   // 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 (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body))
+        if (Thunks.find(&Body) != Thunks.end() ||
+            !Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body))
           continue;
         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->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);
       }
     }
   }
-
-  // Merge all created synthetic ThunkSections back into OutputSection
+  if (AddressesChanged) {
+    // Merge all newly created ThunkSections back into OutputSection
+    mergeThunks();
+    // Update the offsets of each OutputSection we have added ThunkSections to
     for (auto &KV : ThunkSections)
-    mergeThunks(KV.first, KV.second);
-  return !ThunkSections.empty();
+      KV.first->assignOffsets();
+    ++Pass;
+    return true;
+  }
+  return false;
 }
 
 template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64BE>(InputSectionBase &);
 
 template class elf::ThunkCreator<ELF32LE>;
 template class elf::ThunkCreator<ELF32BE>;
 template class elf::ThunkCreator<ELF64LE>;
 template class elf::ThunkCreator<ELF64BE>;

ELF/Writer.cpp

auto AddressesForThunks = [&]() {
         Script->assignAddresses(Phdrs);
       else if (!Config->Relocatable) {
         fixSectionAlignments();
         assignAddresses();
       }
     };
     AddressesForThunks();
     ThunkCreator<ELFT> TC;
-    if (TC.createThunks(OutputSections))
+    while (TC.createThunks(OutputSections)) {
       applySynthetic({In<ELFT>::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
     }
+  }
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();
 
   // createThunks may have added local symbols to the static symbol table
   applySynthetic({In<ELFT>::SymTab, In<ELFT>::ShStrTab, In<ELFT>::StrTab},