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

[peter.smith]

Summary

In preparation for supporting range extension thunks 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 the new ones 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 currently supported thunks we allocate all the thunks on the first pass, the second pass will not result in any more thunks.

[ruiu]

ELF/Relocations.cpp

1098 ↗

(On Diff #101907)

Does this mean you are expecting that it always converges at most two iterations? I'm not sure if that's a correct assumption.

ELF/Relocations.h

129 ↗

(On Diff #101907)

Please add a comment.

[peter.smith]

Thanks for the comments. When range extension thunks are introduced we can no longer guarantee that only 2 passes will be needed so the limit will need to be raised. With the current supported thunks they will all be generated in the first pass, the second pass will find no more thunks. I've added a comment to make that explicit, and have added a comment to Passes as suggested.

[ruiu]

If I expect that it always converges on the first iteration, I wouldn't use a for-loop, but just call createThunks twice and assert that the second return value is always false. You can convert it to a loop later.

[peter.smith]

Thank you for all the comments. I've updated the diff to:

• Remove the skipping of relocations if we are already a ThunkSection, as it is not needed for the current set of thunks.
• Remove AddressesChanged.
• Remove the loop to be replaced with two calls.

There is a type of range extension Thunk that can be used when the target is only just out of range. The contents of the thunk is just a branch instruction, which itself has a limited range and could trigger another thunk. I'm not proposing to implement this type of thunk as it adds quite a bit of additional complexity.

My plan once I've got the existing reviews accepted (D34034, D34035 and D35037) is:

• allocate addresses before creating range thunks.
• pre-create ThunkSections at roughly branch range intervals rather than just at the end of the executable section.
• Add range thunk support, these will be assigned to a ThunkSection in range of the caller
• Add script and non-script test cases

These will most likely be split up into smaller patches than I've identified here.

[peter.smith]

The code still has
TS = make<ThunkSection>(TOS, IS->OutSecOff);
so now we create an extra thunk, no?

Yes you are right. My apologies for not catching that earlier. I've updated the diff to remove it.

lld/trunk/ELF/Relocations.h

 class ThunkSection;
 class Thunk;
 
 class ThunkCreator {
 public:
   // Return true if Thunks have been added to OutputSections
   bool createThunks(ArrayRef<OutputSectionCommand *> 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);
   ThunkSection *getISThunkSec(InputSection *IS, OutputSection *OS);
   void forEachExecInputSection(
       ArrayRef<OutputSectionCommand *> OutputSections,
       std::function<void(OutputSection *, std::vector<InputSection *> *,
                          InputSection *)>
           Fn);
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, uint32_t Type);
-
+  ThunkSection *addThunkSection(OutputSection *OS,
+                                std::vector<InputSection *> *, uint64_t Off);
   // 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<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

lld/trunk/ELF/Relocations.cpp

ThunkSection *ThunkCreator::getOSThunkSec(OutputSection *OS,
                                           std::vector<InputSection *> *ISR) {
   if (CurTS == nullptr) {
     uint32_t Off = 0;
     for (auto *IS : OS->Sections) {
       Off = IS->OutSecOff + IS->getSize();
       if ((IS->Flags & SHF_EXECINSTR) == 0)
         break;
     }
-    CurTS = make<ThunkSection>(OS, Off);
-    ThunkSections[ISR].push_back(CurTS);
+    CurTS = addThunkSection(OS, ISR, Off);
   }
   return CurTS;
 }
 
 ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS, OutputSection *OS) {
   ThunkSection *TS = ThunkedSections.lookup(IS);
   if (TS)
     return TS;
   auto *TOS = IS->getParent();
-  TS = make<ThunkSection>(TOS, IS->OutSecOff);
 
   // Find InputSectionRange within TOS that IS is in
   OutputSectionCommand *C = Script->getCmd(TOS);
   std::vector<InputSection *> *Range = nullptr;
   for (BaseCommand *BC : C->Commands)
     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;
         break;
       }
     }
-  ThunkSections[Range].push_back(TS);
+  TS = addThunkSection(TOS, Range, IS->OutSecOff);
   ThunkedSections[IS] = TS;
   return TS;
 }
 
+ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
+                                            std::vector<InputSection *> *ISR,
+                                            uint64_t Off) {
+  auto *TS = make<ThunkSection>(OS, Off);
+  ThunkSections[ISR].push_back(TS);
+  return TS;
+}
+
+
 std::pair<Thunk *, bool> ThunkCreator::getThunk(SymbolBody &Body,
                                                 uint32_t Type) {
   auto res = ThunkedSymbols.insert({&Body, nullptr});
   if (res.second)
     res.first->second = addThunk(Type, Body);
   return std::make_pair(res.first->second, res.second);
 }
 

 // 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.
 bool ThunkCreator::createThunks(
     ArrayRef<OutputSectionCommand *> OutputSections) {
+  if (Pass > 0)
+    ThunkSections.clear();
+
   // 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.
   forEachExecInputSection(
-      OutputSections, [=](OutputSection *OS,  std::vector<InputSection*> *ISR,
+      OutputSections, [&](OutputSection *OS,  std::vector<InputSection*> *ISR,
                           InputSection *IS) {
         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) {
             // Find or create a ThunkSection for the new Thunk
             ThunkSection *TS;
             if (auto *TIS = T->getTargetInputSection())
               TS = getISThunkSec(TIS, OS);
             else
               TS = getOSThunkSec(OS, ISR);
             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();
+  ++Pass;
   return !ThunkSections.empty();
 }
 
 template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
 template void elf::scanRelocations<ELF64BE>(InputSectionBase &);

lld/trunk/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeSections() {
   if (Target->NeedsThunks) {
     // FIXME: only ARM Interworking and Mips LA25 Thunks are implemented,
     // these
     // do not require address information. To support range extension Thunks
     // we need to assign addresses so that we can tell if jump instructions
     // are out of range. This will need to turn into a loop that converges
     // when no more Thunks are added
     ThunkCreator TC;
-    if (TC.createThunks(OutputSectionCommands))
+    if (TC.createThunks(OutputSectionCommands)) {
       applySynthetic({InX::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
+      if (TC.createThunks(OutputSectionCommands))
+        fatal("All non-range thunks should be created in first call");
+    }
   }
 
   // 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 (OutputSectionCommand *Cmd : OutputSectionCommands)
     Cmd->finalize<ELFT>();