Split InputSectionDescription::Sort into SortInner and SortOuter.

[ruiu]

Summary

The comparator function to compare input sections as instructed by
SORT command was a bit too complicated because it needed to handle
four different cases. This patch split it into two function calls.

This patch also simplifies the parser.

[ruiu]

• Rebased.

[grimar]

I like it, LGTM. Comments below.

ELF/LinkerScript.cpp

142 ↗

(On Diff #66752)

I found a bug, SORT_BY_ALIGNMENT should sort sections into descending order.
Committed fix as r277706.
So condition should be ">" here.

752 ↗

(On Diff #66752)

May be something like:

if (K1 != K2)
Cmd->SortInner = K2;

to avoid double sorting when the same rule is specified twice:
SORT_BY_NAME (SORT_BY_NAME(...))

[grimar]

ELF/LinkerScript.cpp

752 ↗

(On Diff #66752)

Though it seems to be useless cornercase and we probably should not really care, preferring shorter code.

[ruiu]

• Rebased.

[ruiu]

ELF/LinkerScript.cpp

760 ↗

(On Diff #66865)

Yup. Double-sorting is wasteful, but it's probably doesn't have to be handled as an error

[grimar]

lld/trunk/ELF/LinkerScript.cpp

149

btw interesting that gold has an issue here. lld and ld are compatible, but gold sorts by alignment in assending order what
is different from spec and looks like a bug.

lld/trunk/ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   Expr AddrExpr;
   Expr AlignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
-enum class SortKind { None, Name, Align, NameAlign, AlignName };
+enum SortKind { SortNone, SortByName, SortByAlignment };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription() : BaseCommand(InputSectionKind) {}
   static bool classof(const BaseCommand *C);
   StringRef FilePattern;
-  SortKind Sort = SortKind::None;
+  SortKind SortOuter = SortNone;
+  SortKind SortInner = SortNone;
   std::vector<StringRef> ExcludedFiles;
   std::vector<StringRef> SectionPatterns;
 };
 
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
   static bool classof(const BaseCommand *C);
   Expr Expression;

lld/trunk/ELF/LinkerScript.cpp

static void addSection(OutputSectionFactory<ELFT> &Factory,
   OutputSectionBase<ELFT> *Sec;
   bool IsNew;
   std::tie(Sec, IsNew) = Factory.create(C, Name);
   if (IsNew)
     Out.push_back(Sec);
   Sec->addSection(C);
 }
 
-template <class ELFT> struct SectionsSorter {
-  SectionsSorter(SortKind Kind) : Kind(Kind) {}
-  bool operator()(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
-    int AlignmentCmp = A->Alignment - B->Alignment;
-    if (Kind == SortKind::Align || (Kind == SortKind::AlignName && AlignmentCmp != 0))
-      return AlignmentCmp > 0;
-
-    int NameCmp = A->getSectionName().compare(B->getSectionName());
-    if (Kind == SortKind::Name || (Kind == SortKind::NameAlign && NameCmp != 0))
-      return NameCmp < 0;
-
-    if (Kind == SortKind::NameAlign)
-      return AlignmentCmp > 0;
-    if (Kind == SortKind::AlignName)
-      return NameCmp < 0;
+template <class ELFT>
+static bool compareName(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
+  return A->getSectionName() < B->getSectionName();
+}
 
-    llvm_unreachable("unknown section sort kind in predicate");
-    return false;
-  }
-  SortKind Kind;
-};
+template <class ELFT>
+static bool compareAlignment(InputSectionBase<ELFT> *A,
+                             InputSectionBase<ELFT> *B) {
+  // ">" is not a mistake. Larger alignments are placed before smaller
+  // alignments in order to reduce the amount of padding necessary.
+  // This is compatible with GNU.
+  return A->Alignment > B->Alignment;
+}
+
+template <class ELFT>
+static std::function<bool(InputSectionBase<ELFT> *, InputSectionBase<ELFT> *)>
+getComparator(SortKind K) {
+  if (K == SortByName)
+    return compareName<ELFT>;
+  return compareAlignment<ELFT>;
 
 template <class ELFT>
 void LinkerScript<ELFT>::createSections(
     OutputSectionFactory<ELFT> &Factory) {
   for (auto &P : getSectionMap()) {
     StringRef OutputName = P.first;
     const InputSectionDescription *Cmd = P.second;
     std::vector<InputSectionBase<ELFT> *> Sections = getInputSections(Cmd);
 
     if (OutputName == "/DISCARD/") {
       for (InputSectionBase<ELFT> *S : Sections) {
         S->Live = false;
         reportDiscarded(S);
       }
       continue;
     }
 
-    if (Cmd->Sort != SortKind::None)
+    if (Cmd->SortInner)
+      std::stable_sort(Sections.begin(), Sections.end(),
+                       getComparator<ELFT>(Cmd->SortInner));
+    if (Cmd->SortOuter)
       std::stable_sort(Sections.begin(), Sections.end(),
-                       SectionsSorter<ELFT>(Cmd->Sort));
+                       getComparator<ELFT>(Cmd->SortOuter));
 
     for (InputSectionBase<ELFT> *S : Sections)
       addSection(Factory, *OutputSections, S, OutputName);
   }
 
   // Add all other input sections, which are not listed in script.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles())
private:
   SymbolAssignment *readAssignment(StringRef Name);
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription();
   std::vector<StringRef> readInputFilePatterns();
   InputSectionDescription *readInputSectionRules();
   unsigned readPhdrType();
+  SortKind readSortKind();
   SymbolAssignment *readProvide(bool Hidden);
   Expr readAlign();
   void readSort();
   Expr readAssert();
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
   Expr readPrimary();

 
 std::vector<StringRef> ScriptParser::readInputFilePatterns() {
   std::vector<StringRef> V;
   while (!Error && !skip(")"))
     V.push_back(next());
   return V;
 }
 
+SortKind ScriptParser::readSortKind() {
+  if (skip("SORT") || skip("SORT_BY_NAME"))
+    return SortByName;
+  if (skip("SORT_BY_ALIGNMENT"))
+    return SortByAlignment;
+  return SortNone;
+}
+
 InputSectionDescription *ScriptParser::readInputSectionRules() {
   auto *Cmd = new InputSectionDescription;
   Cmd->FilePattern = next();
   expect("(");
 
+  // Read EXCLUDE_FILE().
   if (skip("EXCLUDE_FILE")) {
     expect("(");
     while (!Error && !skip(")"))
       Cmd->ExcludedFiles.push_back(next());
   }
 
-  if (skip("SORT") || skip("SORT_BY_NAME")) {
-    expect("(");
-    if (skip("SORT_BY_ALIGNMENT")) {
-      Cmd->Sort = SortKind::NameAlign;
-      expect("(");
-      Cmd->SectionPatterns = readInputFilePatterns();
-      expect(")");
-    } else {
-      Cmd->Sort = SortKind::Name;
-      Cmd->SectionPatterns = readInputFilePatterns();
-    }
-    expect(")");
-    return Cmd;
-  }
-
-  if (skip("SORT_BY_ALIGNMENT")) {
+  // Read SORT().
+  if (SortKind K1 = readSortKind()) {
+    Cmd->SortOuter = K1;
     expect("(");
-    if (skip("SORT") || skip("SORT_BY_NAME")) {
-      Cmd->Sort = SortKind::AlignName;
+    if (SortKind K2 = readSortKind()) {
+      Cmd->SortInner = K2;
       expect("(");
       Cmd->SectionPatterns = readInputFilePatterns();
       expect(")");
     } else {
-      Cmd->Sort = SortKind::Align;
       Cmd->SectionPatterns = readInputFilePatterns();
     }
     expect(")");
     return Cmd;
   }
 
   Cmd->SectionPatterns = readInputFilePatterns();
   return Cmd;