[LLD][ELF] SHF_LINK_ORDER should sort based on InputSectionDescriptions

[peter.smith]

Summary

This change alters the sorting for OutputSections with the SHF_LINK_ORDER flag in OutputSection::finalize() to use the InputSectionDescription representation and not the OutputSection::Sections representation.

With this change the OutputSections::Sections is no longer operated on for SHF_LINK_ORDER. The synchronize function has been changed to skip sections with SHF_LINK_ORDER as this will undo the ordering done in finalize().

[peter.smith]

On trunk we now have

if (!Script->Opt.HasSections) {
  if (!Config->Relocatable)
    fixSectionAlignments();
  Script->fabricateDefaultCommands();
} else {
  Script->synchronize();
}

Would it be possible to move this block together? That would avoid the need to change synchronize as it would now be earlier too.

I've updated the diff to move the fabricatedDefaultCommands() after ThunkCreation, this permits the block to stay together. Later Today I'm intending to post a set of patches to convert Thunks to insert into InputSectionDescriptions which will hopefully permit synchronize() to be removed.

lld/trunk/ELF/OutputSections.cpp

template <class ELFT> static void finalizeShtGroup(OutputSection *Sec) {
   elf::ObjectFile<ELFT> *Obj = Sec->Sections[0]->getFile<ELFT>();
   assert(Config->Relocatable && Sec->Sections.size() == 1);
   ArrayRef<SymbolBody *> Symbols = Obj->getSymbols();
   Sec->Info = InX::SymTab->getSymbolIndex(Symbols[Sec->Sections[0]->Info - 1]);
 }
 
 template <class ELFT> void OutputSection::finalize() {
   if ((this->Flags & SHF_LINK_ORDER) && !this->Sections.empty()) {
+    OutputSectionCommand *Cmd = Script->getCmd(this);
+    // Link order may be distributed across several InputSectionDescriptions
+    // but sort must consider them all at once.
+    std::vector<InputSection **> ScriptSections;
+    std::vector<InputSection *> Sections;
+    for (BaseCommand *Base : Cmd->Commands)
+      if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
+        for (InputSection *&IS : ISD->Sections) {
+          ScriptSections.push_back(&IS);
+          Sections.push_back(IS);
+        }
     std::sort(Sections.begin(), Sections.end(), compareByFilePosition);
-    assignOffsets();
+    for (int I = 0, N = Sections.size(); I < N; ++I)
+      *ScriptSections[I] = Sections[I];
 
     // We must preserve the link order dependency of sections with the
     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
     // need to translate the InputSection sh_link to the OutputSection sh_link,
     // all InputSections in the OutputSection have the same dependency.
     if (auto *D = this->Sections.front()->getLinkOrderDep())
       this->Link = D->getParent()->SectionIndex;
   }

lld/trunk/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::run() {
   // Now that we have a complete set of output sections. This function
   // completes section contents. For example, we need to add strings
   // to the string table, and add entries to .got and .plt.
   // finalizeSections does that.
   finalizeSections();
   if (ErrorCount)
     return;
 
-  if (!Script->Opt.HasSections)
-    Script->fabricateDefaultCommands();
-  else
-    Script->synchronize();
-
   for (BaseCommand *Base : Script->Opt.Commands)
     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
       OutputSectionCommands.push_back(Cmd);
 
   clearOutputSections();
 
   if (!Script->Opt.HasSections &&!Config->Relocatable)
     fixSectionAlignments();
if (Target->NeedsThunks) {
     // 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(OutputSections))
       applySynthetic({InX::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
   }
+
+  if (!Script->Opt.HasSections)
+    Script->fabricateDefaultCommands();
+  else
+    Script->synchronize();
+
   // 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({InX::SymTab, InX::ShStrTab, InX::StrTab},