[ELF] - Linkerscript: Implemented SORT command.

When the SORT keyword is used, the linker will sort the files or sections into ascending order by name before placing them in the output file.
It is used in FreeBSD script:
https://svnweb.freebsd.org/base/head/sys/conf/ldscript.amd64?revision=284870&view=markup#l139

This is PR28689.

Differential revision: https://reviews.llvm.org/D22749

llvm-svn: 277153

4 files changed, 108 insertions, 6 deletions

diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index 097375a8a66..ed47c74e7a9 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -132,11 +132,18 @@ static void addSection(OutputSectionFactory<ELFT> &Factory,
 }
 
 template <class ELFT>
+static bool compareByName(InputSectionBase<ELFT> *A,
+                          InputSectionBase<ELFT> *B) {
+  return A->getSectionName() < B->getSectionName();
+}
+
+template <class ELFT>
 std::vector<OutputSectionBase<ELFT> *>
 LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
   std::vector<OutputSectionBase<ELFT> *> Ret;
 
   for (auto &P : getSectionMap()) {
+    std::vector<InputSectionBase<ELFT> *> Sections;
     StringRef OutputName = P.first;
     const InputSectionDescription *I = P.second;
     for (InputSectionBase<ELFT> *S : getInputSections(I)) {
@@ -145,8 +152,12 @@ LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
         reportDiscarded(S);
         continue;
       }
-      addSection(Factory, Ret, S, OutputName);
+      Sections.push_back(S);
     }
+    if (I->Sort)
+      std::stable_sort(Sections.begin(), Sections.end(), compareByName<ELFT>);
+    for (InputSectionBase<ELFT> *S : Sections)
+      addSection(Factory, Ret, S, OutputName);
   }
 
   // Add all other input sections, which are not listed in script.
@@ -444,6 +455,7 @@ private:
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   std::unique_ptr<InputSectionDescription> readInputSectionDescription();
+  void readInputFilePattern(InputSectionDescription *InCmd, bool Keep);
   void readInputSectionRules(InputSectionDescription *InCmd, bool Keep);
   unsigned readPhdrType();
   void readProvide(bool Hidden);
@@ -674,7 +686,17 @@ static int precedence(StringRef Op) {
       .Default(-1);
 }
 
-void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd, bool Keep) {
+void ScriptParser::readInputFilePattern(InputSectionDescription *InCmd,
+                                        bool Keep) {
+  while (!Error && !skip(")")) {
+    if (Keep)
+      Opt.KeptSections.push_back(peek());
+    InCmd->SectionPatterns.push_back(next());
+  }
+}
+
+void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd,
+                                         bool Keep) {
   InCmd->FilePattern = next();
   expect("(");
 
@@ -684,11 +706,15 @@ void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd, bool Ke
       InCmd->ExcludedFiles.push_back(next());
   }
 
-  while (!Error && !skip(")")) {
-    if (Keep)
-      Opt.KeptSections.push_back(peek());
-    InCmd->SectionPatterns.push_back(next());
+  if (skip("SORT")) {
+    expect("(");
+    InCmd->Sort = true;
+    readInputFilePattern(InCmd, Keep);
+    expect(")");
+    return;
   }
+
+  readInputFilePattern(InCmd, Keep);
 }
 
 std::unique_ptr<InputSectionDescription>
diff --git a/lld/ELF/LinkerScript.h b/lld/ELF/LinkerScript.h
index 056abdc413e..34996ed2221 100644
--- a/lld/ELF/LinkerScript.h
+++ b/lld/ELF/LinkerScript.h
@@ -91,6 +91,7 @@ struct InputSectionDescription : BaseCommand {
   InputSectionDescription() : BaseCommand(InputSectionKind) {}
   static bool classof(const BaseCommand *C);
   StringRef FilePattern;
+  bool Sort = false;
   std::vector<StringRef> ExcludedFiles;
   std::vector<StringRef> SectionPatterns;
 };
diff --git a/lld/test/ELF/linkerscript/Inputs/linkerscript-sort.s b/lld/test/ELF/linkerscript/Inputs/linkerscript-sort.s
new file mode 100644
index 00000000000..3a8168f8223
--- /dev/null
+++ b/lld/test/ELF/linkerscript/Inputs/linkerscript-sort.s
@@ -0,0 +1,14 @@
+.section .aaa.5, "a"
+.quad 0x55
+
+.section .aaa.1, "a"
+.quad 0x11
+
+.section .aaa.3, "a"
+.quad 0x33
+
+.section .aaa.2, "a"
+.quad 0x22
+
+.section .aaa.4, "a"
+.quad 0x44
diff --git a/lld/test/ELF/linkerscript/linkerscript-sort.s b/lld/test/ELF/linkerscript/linkerscript-sort.s
new file mode 100644
index 00000000000..7a2050a519a
--- /dev/null
+++ b/lld/test/ELF/linkerscript/linkerscript-sort.s
@@ -0,0 +1,61 @@
+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
+# RUN:   %p/Inputs/linkerscript-sort.s -o %t2.o
+
+# RUN: echo "SECTIONS { .aaa : { *(.aaa.*) } }" > %t1.script
+# RUN: ld.lld -o %t1 --script %t1.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t1 | FileCheck -check-prefix=UNSORTED %s
+# UNSORTED:      Contents of section .aaa:
+# UNSORTED-NEXT:   0120 55000000 00000000 11000000 00000000
+# UNSORTED-NEXT:   0130 33000000 00000000 22000000 00000000
+# UNSORTED-NEXT:   0140 44000000 00000000 05000000 00000000
+# UNSORTED-NEXT:   0150 01000000 00000000 03000000 00000000
+# UNSORTED-NEXT:   0160 02000000 00000000 04000000 00000000
+
+## Check that SORT works (sorted by name of section).
+# RUN: echo "SECTIONS { .aaa : { *(SORT(.aaa.*)) } }" > %t2.script
+# RUN: ld.lld -o %t2 --script %t2.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SORTED_A %s
+# SORTED_A:      Contents of section .aaa:
+# SORTED_A-NEXT:  0120 11000000 00000000 01000000 00000000
+# SORTED_A-NEXT:  0130 22000000 00000000 02000000 00000000
+# SORTED_A-NEXT:  0140 33000000 00000000 03000000 00000000
+# SORTED_A-NEXT:  0150 44000000 00000000 04000000 00000000
+# SORTED_A-NEXT:  0160 55000000 00000000 05000000 00000000
+
+## When we switch the order of files, check that sorting by
+## section names is stable.
+# RUN: echo "SECTIONS { .aaa : { *(SORT(.aaa.*)) } }" > %t3.script
+# RUN: ld.lld -o %t3 --script %t3.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_B %s
+# SORTED_B:      Contents of section .aaa:
+# SORTED_B-NEXT:  0120 01000000 00000000 11000000 00000000
+# SORTED_B-NEXT:  0130 02000000 00000000 22000000 00000000
+# SORTED_B-NEXT:  0140 03000000 00000000 33000000 00000000
+# SORTED_B-NEXT:  0150 04000000 00000000 44000000 00000000
+# SORTED_B-NEXT:  0160 05000000 00000000 55000000 00000000
+
+## Check that SORT surrounded with KEEP also works.
+# RUN: echo "SECTIONS { .aaa : { KEEP (*(SORT(.aaa.*))) } }" > %t3.script
+# RUN: ld.lld -o %t3 --script %t3.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_A %s
+
+.global _start
+_start:
+ nop
+
+.section .aaa.5, "a"
+.quad 5
+
+.section .aaa.1, "a"
+.quad 1
+
+.section .aaa.3, "a"
+.quad 3
+
+.section .aaa.2, "a"
+.quad 2
+
+.section .aaa.4, "a"
+.quad 4