[LLD][ELF] Record created ThunkSections in InputSectionDescription [NFC]

[peter.smith]

Summary

This is a refactoring change split out from D34689. It implements the suggestion to move ThunkCreator's map from std::vector<InputSection *> * to std::vector<ThunkSection *> to a vector<ThunkSection *> in InputSectionDescription. This patch implements just this refactoring. There are quite a lot of small changes involved although most are mechanical in nature. Notable changes:

• We must now iterate over the InputSectionDescription to find the new Thunks rather than iterating over the map. I've modified forEachExecInputSection to be forEachInputSectionDescription so this can be used in mergeThunks.
• We cannot clear the InputSectionDescription->ThunkSections within the forEachInputSectionDescription within createThunks as the Mips Thunks are inserted in the callee's InputSectionDescription. I've chosen to clear it after merging all the Thunks.

[pcc]

ELF/Relocations.h

128

This should be a struct, otherwise clang will warn.

[peter.smith]

Thanks very much for spotting that. Updated patch to fix and to rebase in light of recent refactoring.

[peter.smith]

Rebase in light of recent refactoring changes to RelType. No other changes.

[ruiu]

LGTM

ELF/LinkerScript.h

SectionPattern(StringMatcher &&Pat1, StringMatcher &&Pat2)
       : ExcludedFilePat(Pat1), SectionPat(Pat2) {}
 
   StringMatcher ExcludedFilePat;
   StringMatcher SectionPat;
   SortSectionPolicy SortOuter;
   SortSectionPolicy SortInner;
 };
 
+class ThunkSection;
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription(StringRef FilePattern)
       : BaseCommand(InputSectionKind), FilePat(FilePattern) {}
 
   static bool classof(const BaseCommand *C) {
     return C->Kind == InputSectionKind;
   }
 
   StringMatcher FilePat;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> SectionPatterns;
 
   std::vector<InputSection *> Sections;
+
+  // Temporary record of synthetic ThunkSection instances that we need to
+  // insert into Sections at the end of a createThunks() pass.
+  std::vector<ThunkSection *> ThunkSections;
 };
 
 // Represents an ASSERT().
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
 
   static bool classof(const BaseCommand *C) { return C->Kind == AssertKind; }
 

ELF/Relocations.h

struct Relocation {
   int64_t Addend;
   SymbolBody *Sym;
 };
 
 template <class ELFT> void scanRelocations(InputSectionBase &);
 
 class ThunkSection;
 class Thunk;
+struct InputSectionDescription;
 
 class ThunkCreator {
 public:
   // Return true if Thunks have been added to OutputSections
   bool createThunks(ArrayRef<OutputSection *> OutputSections);
 
   // The number of completed passes of createThunks this permits us
   // to do one time initialization on Pass 0 and put a limit on the
   // number of times it can be called to prevent infinite loops.
   uint32_t Pass = 0;
 
 private:
-  void mergeThunks();
-  ThunkSection *getOSThunkSec(OutputSection *OS,
-                              std::vector<InputSection *> *ISR);
+  void mergeThunks(ArrayRef<OutputSection *> OutputSections);
+  ThunkSection *getOSThunkSec(OutputSection *OS, InputSectionDescription *ISD);
   ThunkSection *getISThunkSec(InputSection *IS);
-  void forEachExecInputSection(
+
+  void forEachInputSectionDescription(
       ArrayRef<OutputSection *> OutputSections,
-      std::function<void(OutputSection *, std::vector<InputSection *> *,
-                         InputSection *)>
-          Fn);
+      std::function<void(OutputSection *, InputSectionDescription *)> Fn);
+
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, RelType Type);
-  ThunkSection *addThunkSection(OutputSection *OS,
-                                std::vector<InputSection *> *, uint64_t Off);
+  ThunkSection *addThunkSection(OutputSection *OS, InputSectionDescription *,
+                                uint64_t Off);
   // 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
   // the Thunk from a relocation to the Thunks symbol definition.
   llvm::DenseMap<SymbolBody *, Thunk *> Thunks;
 
   // Track InputSections that have an inline ThunkSection placed in front
   // an inline ThunkSection may have control fall through to the section below
   // so we need to make sure that there is only one of them.
   // The Mips LA25 Thunk is an example of an inline ThunkSection.
   llvm::DenseMap<InputSection *, ThunkSection *> ThunkedSections;
-
-  // 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<std::vector<InputSection *> *, std::vector<ThunkSection *>>
-      ThunkSections;
-
-  // The ThunkSection for this vector of InputSections
-  ThunkSection *CurTS;
 };
 
 // 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;
 }
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/Relocations.cpp

 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
   if (S.AreRelocsRela)
     scanRelocs<ELFT>(S, S.relas<ELFT>());
   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
-void ThunkCreator::mergeThunks() {
-  for (auto &KV : ThunkSections) {
-    std::vector<InputSection *> *ISR = KV.first;
-    std::vector<ThunkSection *> &Thunks = KV.second;
+// Merge the ThunkSections created this pass into the InputSectionDescriptions.
+void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> OutputSections) {
+  forEachInputSectionDescription(
+      OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
+        if (ISD->ThunkSections.empty())
+          return;
 
         // Order Thunks in ascending OutSecOff
-    auto ThunkCmp = [](const ThunkSection *A, const ThunkSection *B) {
+        std::stable_sort(ISD->ThunkSections.begin(), ISD->ThunkSections.end(),
+                         [](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(ISR->size() + Thunks.size());
+        Tmp.reserve(ISD->Sections.size() + ISD->ThunkSections.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.
+            // 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(ISR->begin(), ISR->end(), Thunks.begin(), Thunks.end(),
+        std::merge(ISD->Sections.begin(), ISD->Sections.end(),
+                   ISD->ThunkSections.begin(), ISD->ThunkSections.end(),
                    std::back_inserter(Tmp), MergeCmp);
-    *ISR = std::move(Tmp);
-  }
+        ISD->Sections = std::move(Tmp);
+        ISD->ThunkSections.clear();
+      });
 }
 
 static uint32_t findEndOfFirstNonExec(OutputSection &Cmd) {
   for (BaseCommand *Base : Cmd.SectionCommands)
     if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
       for (auto *IS : ISD->Sections)
         if ((IS->Flags & SHF_EXECINSTR) == 0)
           return IS->OutSecOff + IS->getSize();
   return 0;
 }
 
 ThunkSection *ThunkCreator::getOSThunkSec(OutputSection *OS,
-                                          std::vector<InputSection *> *ISR) {
-  if (CurTS == nullptr) {
-    uint32_t Off = findEndOfFirstNonExec(*OS);
-    CurTS = addThunkSection(OS, ISR, Off);
-  }
-  return CurTS;
+                                          InputSectionDescription *ISD) {
+  if (!ISD->ThunkSections.empty())
+    return ISD->ThunkSections.front();
+
+  return addThunkSection(OS, ISD, Off);
 }
 
 // Add a Thunk that needs to be placed in a ThunkSection that immediately
 // precedes its Target.
 ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS) {
   ThunkSection *TS = ThunkedSections.lookup(IS);
   if (TS)
     return TS;
 
   // Find InputSectionRange within Target Output Section (TOS) that the
   // InputSection (IS) that we need to precede is in.
   OutputSection *TOS = IS->getParent();
-  std::vector<InputSection *> *Range = nullptr;
   for (BaseCommand *BC : TOS->SectionCommands)
     if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
       InputSection *first = ISD->Sections.front();
       InputSection *last = ISD->Sections.back();
       if (IS->OutSecOff >= first->OutSecOff &&
           IS->OutSecOff <= last->OutSecOff) {
-        Range = &ISD->Sections;
+        TS = addThunkSection(TOS, ISD, IS->OutSecOff);
+        ThunkedSections[IS] = TS;
         break;
       }
     }
-  TS = addThunkSection(TOS, Range, IS->OutSecOff);
-  ThunkedSections[IS] = TS;
   return TS;
 }
 
 ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
-                                            std::vector<InputSection *> *ISR,
+                                            InputSectionDescription *ISD,
                                             uint64_t Off) {
   auto *TS = make<ThunkSection>(OS, Off);
-  ThunkSections[ISR].push_back(TS);
+  ISD->ThunkSections.push_back(TS);
   return TS;
 }
 
 std::pair<Thunk *, bool> ThunkCreator::getThunk(SymbolBody &Body,
                                                 RelType Type) {
   auto Res = ThunkedSymbols.insert({&Body, std::vector<Thunk *>()});
   if (!Res.second) {
     // Check existing Thunks for Body to see if they can be reused
     for (Thunk *ET : Res.first->second)
       if (ET->isCompatibleWith(Type))
         return std::make_pair(ET, false);
   }
   // No existing compatible Thunk in range, create a new one
   Thunk *T = addThunk(Type, Body);
   Res.first->second.push_back(T);
   return std::make_pair(T, true);
 }
 
 // Call Fn on every executable InputSection accessed via the linker script
 // InputSectionDescription::Sections.
-void ThunkCreator::forEachExecInputSection(
+void ThunkCreator::forEachInputSectionDescription(
     ArrayRef<OutputSection *> OutputSections,
-    std::function<void(OutputSection *, std::vector<InputSection *> *,
-                       InputSection *)>
-        Fn) {
+    std::function<void(OutputSection *, InputSectionDescription *)> Fn) {
   for (OutputSection *OS : OutputSections) {
     if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
       continue;
     for (BaseCommand *BC : OS->SectionCommands)
-      if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
-        CurTS = nullptr;
-        for (InputSection *IS : ISD->Sections)
-          Fn(OS, &ISD->Sections, IS);
-      }
+      if (auto *ISD = dyn_cast<InputSectionDescription>(BC))
+        Fn(OS, ISD);
   }
 }
 
 // Process all relocations from the InputSections that have been assigned
-// to OutputSections and redirect through Thunks if needed.
+// to InputSectionDescriptions 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.
+// finalized. If any Thunks are added to an InputSectionDescription the
+// offsets within the OutputSection of the InputSections will change.
 //
 // FIXME: All Thunks are assumed to be in range of the relocation. Range
 // extension Thunks are not yet supported.
 bool ThunkCreator::createThunks(ArrayRef<OutputSection *> OutputSections) {
-  if (Pass > 0)
-    ThunkSections.clear();
-
+  bool AddressesChanged = false;
   // Create all the Thunks and insert them into synthetic ThunkSections. The
-  // ThunkSections are later inserted back into the OutputSection.
-
+  // ThunkSections are later inserted back into InputSectionDescriptions.
   // 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.
-  forEachExecInputSection(OutputSections, [&](OutputSection *OS,
-                                              std::vector<InputSection *> *ISR,
-                                              InputSection *IS) {
+  // ThunkSections as ThunkSections are not always inserted into the same
+  // InputSectionDescription as the caller.
+  forEachInputSectionDescription(
+      OutputSections, [&](OutputSection *OS, InputSectionDescription *ISD) {
+        for (InputSection *IS : ISD->Sections)
           for (Relocation &Rel : IS->Relocations) {
             SymbolBody &Body = *Rel.Sym;
             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);
               else
-          TS = getOSThunkSec(OS, ISR);
+                TS = getOSThunkSec(OS, ISD);
               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
-  mergeThunks();
+  mergeThunks(OutputSections);
   ++Pass;
-  return !ThunkSections.empty();
+  return AddressesChanged;
 }
 
 template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64BE>(InputSectionBase &);