Move clearOutputSections before sortSections

[• rafael]

Summary

This is probably the main patch left in unifying our intermediary representation.

It moves the creation of default commands before section sorting. This has the nice effect that we now have one location where we decide where an orphan section should be placed.

Before this patch sortSections would decide the relative location of orphan sections to other sections, but it was up to placeOrphanSection to decide on the exact location.

We now only sort sections we created since the linker script is already in the correct order.

[ruiu]

LGTM

ELF/LinkerScript.cpp

771–772

Can this be just ISD->Sections = Sec->Sections?

[• espindola]

305512

ELF/LinkerScript.h

public:
   void adjustSectionsAfterSorting();
 
   std::vector<PhdrEntry> createPhdrs();
   bool ignoreInterpSection();
 
   bool hasLMA(OutputSection *Sec);
   bool shouldKeep(InputSectionBase *S);
   void assignOffsets(OutputSectionCommand *Cmd);
-  void placeOrphanSections();
+  void createOrphanCommands();
   void processNonSectionCommands();
   void assignAddresses(std::vector<PhdrEntry> &Phdrs);
 
   void addSymbol(SymbolAssignment *Cmd);
   void processCommands(OutputSectionFactory &Factory);
 
   // Parsed linker script configurations are set to this struct.
   ScriptConfiguration Opt;
 };
 
 extern LinkerScript *Script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/LinkerScript.cpp

if (OutputSection *Sec = Cmd->Sec) {
       continue;
     }
 
     if (isAllSectionDescription(*Cmd))
       continue;
 
     auto *OutSec = make<OutputSection>(Cmd->Name, SHT_PROGBITS, Flags);
     OutSec->SectionIndex = I;
-    OutputSections.push_back(OutSec);
     Cmd->Sec = OutSec;
     SecToCommand[OutSec] = Cmd;
   }
 }
 
 void LinkerScript::adjustSectionsAfterSorting() {
-  placeOrphanSections();
-
   // Try and find an appropriate memory region to assign offsets in.
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base)) {
       Cmd->MemRegion = findMemoryRegion(Cmd);
       // Handle align (e.g. ".foo : ALIGN(16) { ... }").
       if (Cmd->AlignExpr)
   Cmd->Sec->updateAlignment(Cmd->AlignExpr().getValue());
     }
if (Cmd->Phdrs.empty())
       Cmd->Phdrs = DefPhdrs;
     else
       DefPhdrs = Cmd->Phdrs;
   }
 
   removeEmptyCommands();
 }
 
-// When placing orphan sections, we want to place them after symbol assignments
-// so that an orphan after
-//   begin_foo = .;
-//   foo : { *(foo) }
-//   end_foo = .;
-// doesn't break the intended meaning of the begin/end symbols.
-// We don't want to go over sections since Writer<ELFT>::sortSections is the
-// one in charge of deciding the order of the sections.
-// We don't want to go over alignments, since doing so in
-//  rx_sec : { *(rx_sec) }
-//  . = ALIGN(0x1000);
-//  /* The RW PT_LOAD starts here*/
-//  rw_sec : { *(rw_sec) }
-// would mean that the RW PT_LOAD would become unaligned.
-static bool shouldSkip(BaseCommand *Cmd) {
-  if (isa<OutputSectionCommand>(Cmd))
-    return false;
-  if (auto *Assign = dyn_cast<SymbolAssignment>(Cmd))
-    return Assign->Name != ".";
-  return true;
-}
-
-// Orphan sections are sections present in the input files which are
-// not explicitly placed into the output file by the linker script.
-//
-// When the control reaches this function, Opt.Commands contains
-// output section commands for non-orphan sections only. This function
-// adds new elements for orphan sections so that all sections are
-// explicitly handled by Opt.Commands.
-//
-// Writer<ELFT>::sortSections has already sorted output sections.
-// What we need to do is to scan OutputSections vector and
-// Opt.Commands in parallel to find orphan sections. If there is an
-// output section that doesn't have a corresponding entry in
-// Opt.Commands, we will insert a new entry to Opt.Commands.
-//
-// There is some ambiguity as to where exactly a new entry should be
-// inserted, because Opt.Commands contains not only output section
-// commands but also other types of commands such as symbol assignment
-// expressions. There's no correct answer here due to the lack of the
-// formal specification of the linker script. We use heuristics to
-// determine whether a new output command should be added before or
-// after another commands. For the details, look at shouldSkip
-// function.
-void LinkerScript::placeOrphanSections() {
-  // The OutputSections are already in the correct order.
-  // This loops creates or moves commands as needed so that they are in the
-  // correct order.
-  int CmdIndex = 0;
-
-  // As a horrible special case, skip the first . assignment if it is before any
-  // section. We do this because it is common to set a load address by starting
-  // the script with ". = 0xabcd" and the expectation is that every section is
-  // after that.
-  auto FirstSectionOrDotAssignment =
-      std::find_if(Opt.Commands.begin(), Opt.Commands.end(),
-                   [](BaseCommand *Cmd) { return !shouldSkip(Cmd); });
-  if (FirstSectionOrDotAssignment != Opt.Commands.end()) {
-    CmdIndex = FirstSectionOrDotAssignment - Opt.Commands.begin();
-    if (isa<SymbolAssignment>(**FirstSectionOrDotAssignment))
-      ++CmdIndex;
-  }
-
+void LinkerScript::createOrphanCommands() {
   for (OutputSection *Sec : OutputSections) {
-    StringRef Name = Sec->Name;
-
-    // Find the last spot where we can insert a command and still get the
-    // correct result.
-    auto CmdIter = Opt.Commands.begin() + CmdIndex;
-    auto E = Opt.Commands.end();
-    while (CmdIter != E && shouldSkip(*CmdIter)) {
-      ++CmdIter;
-      ++CmdIndex;
-    }
-
-    // If there is no command corresponding to this output section,
-    // create one and put a InputSectionDescription in it so that both
-    // representations agree on which input sections to use.
-    OutputSectionCommand *Cmd = getCmd(Sec);
-    if (!Cmd) {
-      Cmd = createOutputSectionCommand(Name, "<internal>");
-      Opt.Commands.insert(CmdIter, Cmd);
-      ++CmdIndex;
-
-      Cmd->Sec = Sec;
-      SecToCommand[Sec] = Cmd;
-      auto *ISD = make<InputSectionDescription>("");
-      for (InputSection *IS : Sec->Sections)
-        ISD->Sections.push_back(IS);
-      Cmd->Commands.push_back(ISD);
-
-      continue;
-    }
-
-    // Continue from where we found it.
-    while (*CmdIter != Cmd) {
-      ++CmdIter;
-      ++CmdIndex;
-    }
-    ++CmdIndex;
+    if (Sec->SectionIndex != INT_MAX)
+      continue;
+    OutputSectionCommand *Cmd =
+        createOutputSectionCommand(Sec->Name, "<internal>");
+    Opt.Commands.push_back(Cmd);
   }
 }
 
 void LinkerScript::processNonSectionCommands() {
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base))
       assignSymbol(Cmd, false);
     else if (auto *Cmd = dyn_cast<AssertCommand>(Base))

ELF/Writer.cpp

for (InputSectionBase *&S : InputSections) {
     S = nullptr;
   }
 
   std::vector<InputSectionBase *> &V = InputSections;
   V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
 }
 
 template <class ELFT> void Writer<ELFT>::clearOutputSections() {
+  if (Script->Opt.HasSections)
+    Script->createOrphanCommands();
+  else
+    Script->fabricateDefaultCommands();
   // Clear the OutputSections to make sure it is not used anymore. Any
   // code from this point on should be using the linker script
   // commands.
   for (OutputSection *Sec : OutputSections)
     Sec->Sections.clear();
   OutputSections.clear();
 }
 
if (Config->EMachine == EM_MIPS) {
 
     if (Sec->Name != ".got")
       Rank |= RF_MIPS_NOT_GOT;
   }
 
   return Rank;
 }
 
-static bool compareSectionsNonScript(const OutputSection *A,
-                                     const OutputSection *B) {
+static bool compareSections(const BaseCommand *ACmd, const BaseCommand *BCmd) {
+  const OutputSection *A = cast<OutputSectionCommand>(ACmd)->Sec;
+  const OutputSection *B = cast<OutputSectionCommand>(BCmd)->Sec;
   if (A->SortRank != B->SortRank)
     return A->SortRank < B->SortRank;
   if (!(A->SortRank & RF_NOT_ADDR_SET))
     return Config->SectionStartMap.lookup(A->Name) <
            Config->SectionStartMap.lookup(B->Name);
   return false;
 }
 
-// Output section ordering is determined by this function.
-static bool compareSections(const OutputSection *A, const OutputSection *B) {
-  // For now, put sections mentioned in a linker script
-  // first. Sections not on linker script will have a SectionIndex of
-  // INT_MAX.
-  int AIndex = A->SectionIndex;
-  int BIndex = B->SectionIndex;
-  if (AIndex != BIndex)
-    return AIndex < BIndex;
-
-  return compareSectionsNonScript(A, B);
-}
-
 void PhdrEntry::add(OutputSection *Sec) {
   Last = Sec;
   if (!First)
     First = Sec;
   p_align = std::max(p_align, Sec->Alignment);
   if (p_type == PT_LOAD)
     Sec->FirstInPtLoad = First;
 }
template <class ELFT> void Writer<ELFT>::createSections() {
   sortCtorsDtors(findSection(".ctors"));
   sortCtorsDtors(findSection(".dtors"));
 }
 
 // We want to find how similar two ranks are.
 // The more branches in getSectionRank that match, the more similar they are.
 // Since each branch corresponds to a bit flag, we can just use
 // countLeadingZeros.
-static unsigned getRankProximity(OutputSection *A, OutputSection *B) {
+static int getRankProximity(OutputSection *A, OutputSection *B) {
   return countLeadingZeros(A->SortRank ^ B->SortRank);
 }
 
+static int getRankProximity(OutputSection *A, BaseCommand *B) {
+  if (auto *Cmd = dyn_cast<OutputSectionCommand>(B))
+    if (Cmd->Sec)
+      return getRankProximity(A, Cmd->Sec);
+  return -1;
+}
+
+// When placing orphan sections, we want to place them after symbol assignments
+// so that an orphan after
+//   begin_foo = .;
+//   foo : { *(foo) }
+//   end_foo = .;
+// doesn't break the intended meaning of the begin/end symbols.
+// We don't want to go over sections since findOrphanPos is the
+// one in charge of deciding the order of the sections.
+// We don't want to go over changes to '.', since doing so in
+//  rx_sec : { *(rx_sec) }
+//  . = ALIGN(0x1000);
+//  /* The RW PT_LOAD starts here*/
+//  rw_sec : { *(rw_sec) }
+// would mean that the RW PT_LOAD would become unaligned.
+static bool shouldSkip(BaseCommand *Cmd) {
+  if (isa<OutputSectionCommand>(Cmd))
+    return false;
+  if (auto *Assign = dyn_cast<SymbolAssignment>(Cmd))
+    return Assign->Name != ".";
+  return true;
+}
+
 // We want to place orphan sections so that they share as much
 // characteristics with their neighbors as possible. For example, if
 // both are rw, or both are tls.
 template <typename ELFT>
-static std::vector<OutputSection *>::iterator
-findOrphanPos(std::vector<OutputSection *>::iterator B,
-              std::vector<OutputSection *>::iterator E) {
-  OutputSection *Sec = *E;
+static std::vector<BaseCommand *>::iterator
+findOrphanPos(std::vector<BaseCommand *>::iterator B,
+              std::vector<BaseCommand *>::iterator E) {
+  OutputSection *Sec = cast<OutputSectionCommand>(*E)->Sec;
 
   // Find the first element that has as close a rank as possible.
-  auto I = std::max_element(B, E, [=](OutputSection *A, OutputSection *B) {
+  auto I = std::max_element(B, E, [=](BaseCommand *A, BaseCommand *B) {
     return getRankProximity(Sec, A) < getRankProximity(Sec, B);
   });
   if (I == E)
     return E;
 
   // Consider all existing sections with the same proximity.
-  unsigned Proximity = getRankProximity(Sec, *I);
-  while (I != E && getRankProximity(Sec, *I) == Proximity &&
-         Sec->SortRank >= (*I)->SortRank)
+  int Proximity = getRankProximity(Sec, *I);
+  for (; I != E; ++I) {
+    auto *Cmd = dyn_cast<OutputSectionCommand>(*I);
+    if (!Cmd || !Cmd->Sec)
+      continue;
+    if (getRankProximity(Sec, Cmd->Sec) != Proximity ||
+        Sec->SortRank < Cmd->Sec->SortRank)
+      break;
+  }
+  auto J = std::find_if(
+      make_reverse_iterator(I), make_reverse_iterator(B),
+      [](BaseCommand *Cmd) { return isa<OutputSectionCommand>(Cmd); });
+  I = J.base();
+  while (I != E && shouldSkip(*I))
     ++I;
   return I;
 }
 
 template <class ELFT> void Writer<ELFT>::sortSections() {
   // Don't sort if using -r. It is not necessary and we want to preserve the
   // relative order for SHF_LINK_ORDER sections.
   if (Config->Relocatable)
     return;
 
   if (Script->Opt.HasSections)
     Script->adjustSectionsBeforeSorting();
 
-  for (OutputSection *Sec : OutputSections)
+  for (BaseCommand *Base : Script->Opt.Commands)
+    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
+      if (OutputSection *Sec = Cmd->Sec)
         Sec->SortRank = getSectionRank(Sec);
 
   if (!Script->Opt.HasSections) {
-    std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                     compareSectionsNonScript);
+    // We know that all the OutputSectionCommands are contiguous in
+    // this case.
+    auto E = Script->Opt.Commands.end();
+    auto I = Script->Opt.Commands.begin();
+    auto IsSection = [](BaseCommand *Base) {
+      return isa<OutputSectionCommand>(Base);
+    };
+    I = std::find_if(I, E, IsSection);
+    E = std::find_if(make_reverse_iterator(E), make_reverse_iterator(I),
+                     IsSection)
+            .base();
+    std::stable_sort(I, E, compareSections);
     return;
   }
 
+  // Orphan sections are sections present in the input files which are
+  // not explicitly placed into the output file by the linker script.
+  //
+  // The sections in the linker script are already in the correct
+  // order. We have to figuere out where to insert the orphan
+  // sections.
+  //
   // The order of the sections in the script is arbitrary and may not agree with
-  // compareSectionsNonScript. This means that we cannot easily define a
-  // strict weak ordering. To see why, consider a comparison of a section in the
-  // script and one not in the script. We have a two simple options:
+  // compareSections. This means that we cannot easily define a strict weak
+  // ordering. To see why, consider a comparison of a section in the script and
+  // one not in the script. We have a two simple options:
   // * Make them equivalent (a is not less than b, and b is not less than a).
   //   The problem is then that equivalence has to be transitive and we can
   //   have sections a, b and c with only b in a script and a less than c
   //   which breaks this property.
   // * Use compareSectionsNonScript. Given that the script order doesn't have
   //   to match, we can end up with sections a, b, c, d where b and c are in the
   //   script and c is compareSectionsNonScript less than b. In which case d
   //   can be equivalent to c, a to b and d < a. As a concrete example:
   //   .a (rx) # not in script
   //   .b (rx) # in script
   //   .c (ro) # in script
   //   .d (ro) # not in script
   //
   // The way we define an order then is:
-  // *  First put script sections at the start and sort the script sections.
-  // *  Move each non-script section to its preferred position. We try
+  // *  Sort only the orphan sections. They are in the end right now.
+  // *  Move each orphan section to its preferred position. We try
   //    to put each section in the last position where it it can share
   //    a PT_LOAD.
+  //
+  // There is some ambiguity as to where exactly a new entry should be
+  // inserted, because Opt.Commands contains not only output section
+  // commands but also other types of commands such as symbol assignment
+  // expressions. There's no correct answer here due to the lack of the
+  // formal specification of the linker script. We use heuristics to
+  // determine whether a new output command should be added before or
+  // after another commands. For the details, look at shouldSkip
+  // function.
+
+  auto I = Script->Opt.Commands.begin();
+  auto E = Script->Opt.Commands.end();
+  auto NonScriptI = std::find_if(I, E, [](BaseCommand *Base) {
+    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
+      return Cmd->Sec && Cmd->Sec->SectionIndex == INT_MAX;
+    return false;
+  });
 
-  std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                   compareSections);
+  // Sort the orphan sections.
+  std::stable_sort(NonScriptI, E, compareSections);
+
+  // As a horrible special case, skip the first . assignment if it is before any
+  // section. We do this because it is common to set a load address by starting
+  // the script with ". = 0xabcd" and the expectation is that every section is
+  // after that.
+  auto FirstSectionOrDotAssignment =
+      std::find_if(I, E, [](BaseCommand *Cmd) { return !shouldSkip(Cmd); });
+  if (FirstSectionOrDotAssignment != E &&
+      isa<SymbolAssignment>(**FirstSectionOrDotAssignment))
+    ++FirstSectionOrDotAssignment;
+  I = FirstSectionOrDotAssignment;
 
-  auto I = OutputSections.begin();
-  auto E = OutputSections.end();
-  auto NonScriptI =
-      std::find_if(OutputSections.begin(), E,
-                   [](OutputSection *S) { return S->SectionIndex == INT_MAX; });
   while (NonScriptI != E) {
     auto Pos = findOrphanPos<ELFT>(I, NonScriptI);
+    OutputSection *Orphan = cast<OutputSectionCommand>(*NonScriptI)->Sec;
 
     // As an optimization, find all sections with the same sort rank
     // and insert them with one rotate.
-    unsigned Rank = (*NonScriptI)->SortRank;
-    auto End = std::find_if(NonScriptI + 1, E, [=](OutputSection *Sec) {
-      return Sec->SortRank != Rank;
+    unsigned Rank = Orphan->SortRank;
+    auto End = std::find_if(NonScriptI + 1, E, [=](BaseCommand *Cmd) {
+      return cast<OutputSectionCommand>(Cmd)->Sec->SortRank != Rank;
     });
     std::rotate(Pos, NonScriptI, End);
     NonScriptI = End;
   }
 
   Script->adjustSectionsAfterSorting();
 }
 
template <class ELFT> void Writer<ELFT>::finalizeSections() {
 
   // Do not proceed if there was an undefined symbol.
   if (ErrorCount)
     return;
 
   addPredefinedSections();
   removeUnusedSyntheticSections(OutputSections);
 
+  clearOutputSections();
   sortSections();
-  if (!Script->Opt.HasSections)
-    Script->fabricateDefaultCommands();
+
+  // Now that we have the final list, create a list of all the
+  // OutputSectionCommands for convenience.
   for (BaseCommand *Base : Script->Opt.Commands)
     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
       OutputSectionCommands.push_back(Cmd);
-  clearOutputSections();
 
   // This is a bit of a hack. A value of 0 means undef, so we set it
   // to 1 t make __ehdr_start defined. The section number is not
   // particularly relevant.
   Out::ElfHeader->SectionIndex = 1;
 
   unsigned I = 1;
   for (OutputSectionCommand *Cmd : OutputSectionCommands) {