[Mips] Implement .{ctors,dtors}.<priority> sections ordering.

Arrange .ctors/.dtors sections in the following order:
  .ctors from crtbegin.o or crtbegin?.o
  .ctors from regular object files
  .ctors.* (sorted) from regular object files
  .ctors from crtend.o or crtend?.o

This order is specific for MIPS traget. For example, on X86
the .ctors.* sections are merged into the .init_array section.

llvm-svn: 209987

6 files changed, 282 insertions, 0 deletions

diff --git a/lld/lib/ReaderWriter/ELF/Mips/CMakeLists.txt b/lld/lib/ReaderWriter/ELF/Mips/CMakeLists.txt
index 9101ac1b8a8..0b0d4b1dddf 100644
--- a/lld/lib/ReaderWriter/ELF/Mips/CMakeLists.txt
+++ b/lld/lib/ReaderWriter/ELF/Mips/CMakeLists.txt
@@ -1,4 +1,5 @@
 add_lld_library(lldMipsELFTarget
+  MipsCtorsOrderPass.cpp
   MipsLinkingContext.cpp
   MipsRelocationHandler.cpp
   MipsRelocationPass.cpp
diff --git a/lld/lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.cpp b/lld/lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.cpp
new file mode 100644
index 00000000000..0a3973afde4
--- /dev/null
+++ b/lld/lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.cpp
@@ -0,0 +1,74 @@
+//===- lib/ReaderWriter/ELF/Mips/Mips/CtorsOrderPass.cpp ------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "MipsCtorsOrderPass.h"
+
+#include <algorithm>
+#include <climits>
+
+using namespace lld;
+using namespace lld::elf;
+
+static bool matchCrtObjName(StringRef objName, StringRef objPath) {
+  if (!objPath.endswith(".o"))
+    return false;
+
+  // check *<objName> case
+  objPath = objPath.drop_back(2);
+  if (objPath.endswith(objName))
+    return true;
+
+  // check *<objName>? case
+  return !objPath.empty() && objPath.drop_back(1).endswith(objName);
+}
+
+static int32_t getSectionPriority(StringRef path, StringRef sectionName) {
+  // Arrange .ctors/.dtors sections in the following order:
+  //   .ctors from crtbegin.o or crtbegin?.o
+  //   .ctors from regular object files
+  //   .ctors.* (sorted) from regular object files
+  //   .ctors from crtend.o or crtend?.o
+
+  if (matchCrtObjName("crtbegin", path))
+    return std::numeric_limits<int32_t>::min();
+  if (matchCrtObjName("crtend", path))
+    return std::numeric_limits<int32_t>::max();
+
+  StringRef num = sectionName.drop_front().rsplit('.').second;
+
+  int32_t priority = std::numeric_limits<int32_t>::min() + 1;
+  if (!num.empty())
+    num.getAsInteger(10, priority);
+
+  return priority;
+}
+
+void MipsCtorsOrderPass::perform(std::unique_ptr<MutableFile> &f) {
+  auto definedAtoms = f->definedAtoms();
+
+  auto last = std::stable_partition(definedAtoms.begin(), definedAtoms.end(),
+                                    [](const DefinedAtom *atom) {
+    if (atom->sectionChoice() != DefinedAtom::sectionCustomRequired)
+      return false;
+
+    StringRef name = atom->customSectionName();
+    return name.startswith(".ctors") || name.startswith(".dtors");
+  });
+
+  std::stable_sort(definedAtoms.begin(), last,
+                   [](const DefinedAtom *left, const DefinedAtom *right) {
+    StringRef leftSec = left->customSectionName();
+    StringRef rightSec = right->customSectionName();
+
+    int32_t leftPriority = getSectionPriority(left->file().path(), leftSec);
+    int32_t rightPriority = getSectionPriority(right->file().path(), rightSec);
+
+    return leftPriority < rightPriority;
+  });
+}
diff --git a/lld/lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.h b/lld/lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.h
new file mode 100644
index 00000000000..eeb1a194f9c
--- /dev/null
+++ b/lld/lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.h
@@ -0,0 +1,25 @@
+//===- lib/ReaderWriter/ELF/Mips/MipsCtorsOrderPass.h ---------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_READER_WRITER_ELF_MIPS_MIPS_CTORS_ORDER_PASS_H
+#define LLD_READER_WRITER_ELF_MIPS_MIPS_CTORS_ORDER_PASS_H
+
+#include "lld/Core/Pass.h"
+
+namespace lld {
+namespace elf {
+/// \brief This pass sorts atoms in .{ctors,dtors}.<priority> sections.
+class MipsCtorsOrderPass : public Pass {
+public:
+  void perform(std::unique_ptr<MutableFile> &mergedFile) override;
+};
+}
+}
+
+#endif
diff --git a/lld/lib/ReaderWriter/ELF/Mips/MipsLinkingContext.cpp b/lld/lib/ReaderWriter/ELF/Mips/MipsLinkingContext.cpp
index b4f73ed6459..9e0e81d3534 100644
--- a/lld/lib/ReaderWriter/ELF/Mips/MipsLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/ELF/Mips/MipsLinkingContext.cpp
@@ -8,6 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "Atoms.h"
+#include "MipsCtorsOrderPass.h"
 #include "MipsLinkingContext.h"
 #include "MipsRelocationPass.h"
 #include "MipsTargetHandler.h"
@@ -44,6 +45,7 @@ void MipsLinkingContext::addPasses(PassManager &pm) {
   if (pass)
     pm.add(std::move(pass));
   ELFLinkingContext::addPasses(pm);
+  pm.add(std::unique_ptr<Pass>(new elf::MipsCtorsOrderPass()));
 }
 
 bool MipsLinkingContext::isDynamicRelocation(const DefinedAtom &,
diff --git a/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h b/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h
index b2eb496a8c5..fb5fbddff12 100644
--- a/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h
+++ b/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h
@@ -43,6 +43,23 @@ public:
                                                  order);
   }
 
+  StringRef getSectionName(const DefinedAtom *da) const override {
+    return llvm::StringSwitch<StringRef>(da->customSectionName())
+        .StartsWith(".ctors", ".ctors")
+        .StartsWith(".dtors", ".dtors")
+        .Default(TargetLayout<ELFType>::getSectionName(da));
+  }
+
+  Layout::SegmentType getSegmentType(Section<ELFType> *section) const override {
+    switch (section->order()) {
+    case DefaultLayout<ELFType>::ORDER_CTORS:
+    case DefaultLayout<ELFType>::ORDER_DTORS:
+      return llvm::ELF::PT_LOAD;
+    default:
+      return TargetLayout<ELFType>::getSegmentType(section);
+    }
+  }
+
   /// \brief GP offset relative to .got section.
   uint64_t getGPOffset() const { return 0x7FF0; }
 
diff --git a/lld/test/elf/Mips/ctors-order.test b/lld/test/elf/Mips/ctors-order.test
new file mode 100644
index 00000000000..bded11a0a2b
--- /dev/null
+++ b/lld/test/elf/Mips/ctors-order.test
@@ -0,0 +1,163 @@
+# Check ordering of .ctors.* sections.
+
+# RUN: yaml2obj -format=elf -docnum 1 %s > %t-crtbeginS.o
+# RUN: yaml2obj -format=elf -docnum 2 %s > %t-crtendS.o
+# RUN: yaml2obj -format=elf -docnum 3 %s > %t-obj.o
+# RUN: lld -flavor gnu -target mipsel -shared --output-filetype=yaml \
+# RUN:     %t-crtbeginS.o %t-obj.o %t-crtendS.o | FileCheck %s
+
+# CHECK:      defined-atoms:
+# CHECK-NEXT:   - ref-name:        L000
+# CHECK-NEXT:     type:            data
+# CHECK-NEXT:     alignment:       2^2
+# CHECK-NEXT:     section-choice:  custom-required
+# CHECK-NEXT:     section-name:    .ctors
+# CHECK-NEXT:     references:
+# CHECK-NEXT:       - kind:            layout-after
+# CHECK-NEXT:         offset:          0
+# CHECK-NEXT:         target:          __CTOR_LIST__
+# CHECK-NEXT:   - name:            __CTOR_LIST__
+# CHECK-NEXT:     type:            data
+# CHECK-NEXT:     content:         [ FF, FF, FF, FF ]
+# CHECK-NEXT:     alignment:       2^2
+# CHECK-NEXT:     section-choice:  custom-required
+# CHECK-NEXT:     section-name:    .ctors
+# CHECK-NEXT:     references:
+# CHECK-NEXT:       - kind:            in-group
+# CHECK-NEXT:         offset:          0
+# CHECK-NEXT:         target:          L000
+# CHECK-NEXT:   - type:            data
+# CHECK-NEXT:     content:         [ 11, 11, 11, 11 ]
+# CHECK-NEXT:     alignment:       2^2
+# CHECK-NEXT:     section-choice:  custom-required
+# CHECK-NEXT:     section-name:    .ctors.1
+# CHECK-NEXT:   - type:            data
+# CHECK-NEXT:     content:         [ 22, 22, 22, 22 ]
+# CHECK-NEXT:     alignment:       2^2
+# CHECK-NEXT:     section-choice:  custom-required
+# CHECK-NEXT:     section-name:    .ctors.2
+# CHECK-NEXT:   - ref-name:        L005
+# CHECK-NEXT:     type:            data
+# CHECK-NEXT:     alignment:       2^2
+# CHECK-NEXT:     section-choice:  custom-required
+# CHECK-NEXT:     section-name:    .ctors
+# CHECK-NEXT:     references:
+# CHECK-NEXT:       - kind:            layout-after
+# CHECK-NEXT:         offset:          0
+# CHECK-NEXT:         target:          __CTOR_END__
+# CHECK-NEXT:   - name:            __CTOR_END__
+# CHECK-NEXT:     type:            data
+# CHECK-NEXT:     content:         [ 00, 00, 00, 00 ]
+# CHECK-NEXT:     alignment:       2^2
+# CHECK-NEXT:     section-choice:  custom-required
+# CHECK-NEXT:     section-name:    .ctors
+
+# crtbeginS.o
+---
+FileHeader:
+  Class:           ELFCLASS32
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_MIPS
+  Flags:           [ EF_MIPS_NOREORDER, EF_MIPS_CPIC,
+                     EF_MIPS_ABI_O32, EF_MIPS_ARCH_32R2 ]
+Sections:
+  - Name:            .ctors
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x04
+    Content:         'FFFFFFFF'
+
+Symbols:
+  Local:
+    - Name:            .ctors
+      Type:            STT_SECTION
+      Section:         .ctors
+    - Name:            __CTOR_LIST__
+      Type:            STT_OBJECT
+      Section:         .ctors
+
+# crtendS.o
+---
+FileHeader:
+  Class:           ELFCLASS32
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_MIPS
+  Flags:           [ EF_MIPS_NOREORDER, EF_MIPS_CPIC,
+                     EF_MIPS_ABI_O32, EF_MIPS_ARCH_32R2 ]
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x04
+    Size:            0x0F
+  - Name:            .rel.text
+    Type:            SHT_REL
+    Link:            .symtab
+    Info:            .text
+    AddressAlign:    0x04
+    Relocations:
+      - Offset:          0x00
+        Symbol:          .ctors
+        Type:            R_MIPS_HI16
+      - Offset:          0x04
+        Symbol:          .ctors
+        Type:            R_MIPS_LO16
+      - Offset:          0x08
+        Symbol:          .ctors
+        Type:            R_MIPS_HI16
+      - Offset:          0x0C
+        Symbol:          .ctors
+        Type:            R_MIPS_LO16
+  - Name:            .ctors
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x04
+    Size:            0x04
+
+Symbols:
+  Local:
+    - Name:            .text
+      Type:            STT_SECTION
+      Section:         .text
+    - Name:            .ctors
+      Type:            STT_SECTION
+      Section:         .ctors
+    - Name:            __CTOR_END__
+      Type:            STT_OBJECT
+      Section:         .ctors
+    - Name:            __do_global_ctors_aux
+      Type:            STT_FUNC
+      Section:         .text
+
+# obj.o
+---
+FileHeader:
+  Class:           ELFCLASS32
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_MIPS
+  Flags:           [ EF_MIPS_NOREORDER, EF_MIPS_CPIC,
+                     EF_MIPS_ABI_O32, EF_MIPS_ARCH_32 ]
+Sections:
+  - Name:            .ctors.2
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x04
+    Content:         '22222222'
+  - Name:            .ctors.1
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x04
+    Content:         '11111111'
+
+Symbols:
+  Local:
+    - Name:            .ctors.2
+      Type:            STT_SECTION
+      Section:         .ctors.2
+    - Name:            .ctors.1
+      Type:            STT_SECTION
+      Section:         .ctors.1
+...