[ELF] - Implemented -z combrelocs/nocombreloc.

This is the option which sorts relocs to optimize dynamic linker performance.
-z combelocs is the default in gold, also it ignores -z nocombreloc,
this patch do the same.

Patch sorts relocations by symbols only and do not create any
DT_REL[A]COUNT entries. That is different with what gold/bfd do.

More information about option is here:
http://www.airs.com/blog/archives/186
http://people.redhat.com/jakub/prelink.pdf, p.2

Differential revision: http://reviews.llvm.org/D19528

llvm-svn: 269066

15 files changed, 130 insertions, 17 deletions

diff --git a/lld/ELF/Config.h b/lld/ELF/Config.h
index fd7dbc2..ade684c 100644
--- a/lld/ELF/Config.h
+++ b/lld/ELF/Config.h
@@ -88,6 +88,7 @@ struct Configuration {
   bool Verbose;
   bool VersionScript = false;
   bool WarnCommon;
+  bool ZCombreloc;
   bool ZExecStack;
   bool ZNodelete;
   bool ZNow;
diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp
index 9a6be7d..f23db3d 100644
--- a/lld/ELF/Driver.cpp
+++ b/lld/ELF/Driver.cpp
@@ -352,6 +352,7 @@ void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   if (Config->LtoJobs == 0)
     error("number of threads must be > 0");
 
+  Config->ZCombreloc = !hasZOption(Args, "nocombreloc");
   Config->ZExecStack = hasZOption(Args, "execstack");
   Config->ZNodelete = hasZOption(Args, "nodelete");
   Config->ZNow = hasZOption(Args, "now");
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 9a44339..676eb80 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -301,9 +301,10 @@ template <class ELFT> void PltSection<ELFT>::finalize() {
 }
 
 template <class ELFT>
-RelocationSection<ELFT>::RelocationSection(StringRef Name)
+RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
     : OutputSectionBase<ELFT>(Name, Config->Rela ? SHT_RELA : SHT_REL,
-                              SHF_ALLOC) {
+                              SHF_ALLOC),
+      Sort(Sort) {
   this->Header.sh_entsize = Config->Rela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
   this->Header.sh_addralign = sizeof(uintX_t);
 }
@@ -313,7 +314,13 @@ void RelocationSection<ELFT>::addReloc(const DynamicReloc<ELFT> &Reloc) {
   Relocs.push_back(Reloc);
 }
 
+template <class ELFT, class RelTy>
+static bool compRelocations(const RelTy &A, const RelTy &B) {
+  return A.getSymbol(Config->Mips64EL) < B.getSymbol(Config->Mips64EL);
+}
+
 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
+  uint8_t *BufBegin = Buf;
   for (const DynamicReloc<ELFT> &Rel : Relocs) {
     auto *P = reinterpret_cast<Elf_Rela *>(Buf);
     Buf += Config->Rela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
@@ -325,6 +332,16 @@ template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
     uint32_t SymIdx = (!Rel.UseSymVA && Sym) ? Sym->DynsymIndex : 0;
     P->setSymbolAndType(SymIdx, Rel.Type, Config->Mips64EL);
   }
+
+  if (Sort) {
+    if (Config->Rela)
+      std::stable_sort((Elf_Rela *)BufBegin,
+                       (Elf_Rela *)BufBegin + Relocs.size(),
+                       compRelocations<ELFT, Elf_Rela>);
+    else
+      std::stable_sort((Elf_Rel *)BufBegin, (Elf_Rel *)BufBegin + Relocs.size(),
+                       compRelocations<ELFT, Elf_Rel>);
+  }
 }
 
 template <class ELFT> unsigned RelocationSection<ELFT>::getRelocOffset() {
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index d8c0e5b..b94f765 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -274,7 +274,7 @@ class RelocationSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
 
 public:
-  RelocationSection(StringRef Name);
+  RelocationSection(StringRef Name, bool Sort);
   void addReloc(const DynamicReloc<ELFT> &Reloc);
   unsigned getRelocOffset();
   void finalize() override;
@@ -284,6 +284,7 @@ public:
   bool Static = false;
 
 private:
+  bool Sort;
   std::vector<DynamicReloc<ELFT>> Relocs;
 };
 
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index c568d71..4c9be04 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -129,7 +129,8 @@ template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
   GotSection<ELFT> Got;
   InterpSection<ELFT> Interp;
   PltSection<ELFT> Plt;
-  RelocationSection<ELFT> RelaDyn(Config->Rela ? ".rela.dyn" : ".rel.dyn");
+  RelocationSection<ELFT> RelaDyn(Config->Rela ? ".rela.dyn" : ".rel.dyn",
+                                  Config->ZCombreloc);
   StringTableSection<ELFT> DynStrTab(".dynstr", true);
   StringTableSection<ELFT> ShStrTab(".shstrtab", false);
   SymbolTableSection<ELFT> DynSymTab(*Symtab, DynStrTab);
@@ -165,7 +166,7 @@ template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
   if (Target->UseLazyBinding) {
     StringRef S = Config->Rela ? ".rela.plt" : ".rel.plt";
     GotPlt.reset(new GotPltSection<ELFT>);
-    RelaPlt.reset(new RelocationSection<ELFT>(S));
+    RelaPlt.reset(new RelocationSection<ELFT>(S, false /*Sort*/));
   }
   if (!Config->StripAll) {
     StrTab.reset(new StringTableSection<ELFT>(".strtab", false));
diff --git a/lld/test/ELF/aarch64-abs64-dyn.s b/lld/test/ELF/aarch64-abs64-dyn.s
index d1242c2..2220225 100644
--- a/lld/test/ELF/aarch64-abs64-dyn.s
+++ b/lld/test/ELF/aarch64-abs64-dyn.s
@@ -17,8 +17,8 @@ bar:
 // RUN: llvm-readobj -symbols -dyn-relocations %t.so | FileCheck %s
 
 // CHECK:      Dynamic Relocations {
-// CHECK-NEXT:   {{.*}} R_AARCH64_ABS64 foo 0x0
 // CHECK-NEXT:   {{.*}} R_AARCH64_RELATIVE - [[BAR_ADDR:.*]]
+// CHECK-NEXT:   {{.*}} R_AARCH64_ABS64 foo 0x0
 // CHECK-NEXT: }
 
 // CHECK:      Symbols [
diff --git a/lld/test/ELF/aarch64-tls-ie.s b/lld/test/ELF/aarch64-tls-ie.s
index 0462add..7e69055 100644
--- a/lld/test/ELF/aarch64-tls-ie.s
+++ b/lld/test/ELF/aarch64-tls-ie.s
@@ -24,8 +24,8 @@
 #RELOC-NEXT: }
 #RELOC:      Relocations [
 #RELOC-NEXT:  Section ({{.*}}) .rela.dyn {
-#RELOC-NEXT:    0x120B0 R_AARCH64_TLS_TPREL64 foo 0x0
 #RELOC-NEXT:    0x120B8 R_AARCH64_TLS_TPREL64 bar 0x0
+#RELOC-NEXT:    0x120B0 R_AARCH64_TLS_TPREL64 foo 0x0
 #RELOC-NEXT:  }
 #RELOC-NEXT:]
 
diff --git a/lld/test/ELF/combrelocs.s b/lld/test/ELF/combrelocs.s
new file mode 100644
index 0000000..5b876ee
--- /dev/null
+++ b/lld/test/ELF/combrelocs.s
@@ -0,0 +1,92 @@
+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld -shared %t.o -o %t.out
+# RUN: llvm-readobj -r --expand-relocs --dynamic-table %t.out | FileCheck %s
+
+# CHECK:      Relocations [
+# CHECK-NEXT:   Section ({{.*}}) .rela.dyn {
+# CHECK-NEXT:     Relocation {
+# CHECK-NEXT:       Offset: 0x2000
+# CHECK-NEXT:       Type: R_X86_64_64
+# CHECK-NEXT:       Symbol: aaa (1)
+# CHECK-NEXT:       Addend: 0x0
+# CHECK-NEXT:     }
+# CHECK-NEXT:     Relocation {
+# CHECK-NEXT:       Offset: 0x2018
+# CHECK-NEXT:       Type: R_X86_64_64
+# CHECK-NEXT:       Symbol: aaa (1)
+# CHECK-NEXT:       Addend: 0x0
+# CHECK-NEXT:     }
+# CHECK-NEXT:     Relocation {
+# CHECK-NEXT:       Offset: 0x2010
+# CHECK-NEXT:       Type: R_X86_64_64
+# CHECK-NEXT:       Symbol: bbb (2)
+# CHECK-NEXT:       Addend: 0x0
+# CHECK-NEXT:     }
+# CHECK-NEXT:     Relocation {
+# CHECK-NEXT:       Offset: 0x2008
+# CHECK-NEXT:       Type: R_X86_64_64
+# CHECK-NEXT:       Symbol: ccc (3)
+# CHECK-NEXT:       Addend: 0x0
+# CHECK-NEXT:     }
+# CHECK-NEXT:     Relocation {
+# CHECK-NEXT:       Offset: 0x2020
+# CHECK-NEXT:       Type: R_X86_64_64
+# CHECK-NEXT:       Symbol: ddd (4)
+# CHECK-NEXT:       Addend: 0x0
+# CHECK-NEXT:     }
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+# CHECK:      DynamicSection [
+# CHECK-NEXT:   Tag
+# CHECK-NOT:    RELACOUNT
+
+# RUN: ld.lld -z nocombreloc -shared %t.o -o %t.out
+# RUN: llvm-readobj -r --expand-relocs --dynamic-table %t.out | \
+# RUN:    FileCheck --check-prefix=NOCOMB %s
+
+# NOCOMB:      Relocations [
+# NOCOMB-NEXT:    Section ({{.*}}) .rela.dyn {
+# NOCOMB-NEXT:     Relocation {
+# NOCOMB-NEXT:       Offset: 0x2000
+# NOCOMB-NEXT:       Type: R_X86_64_64
+# NOCOMB-NEXT:       Symbol: aaa (1)
+# NOCOMB-NEXT:       Addend: 0x0
+# NOCOMB-NEXT:     }
+# NOCOMB-NEXT:     Relocation {
+# NOCOMB-NEXT:       Offset: 0x2008
+# NOCOMB-NEXT:       Type: R_X86_64_64
+# NOCOMB-NEXT:       Symbol: ccc (3)
+# NOCOMB-NEXT:       Addend: 0x0
+# NOCOMB-NEXT:     }
+# NOCOMB-NEXT:     Relocation {
+# NOCOMB-NEXT:       Offset: 0x2010
+# NOCOMB-NEXT:       Type: R_X86_64_64
+# NOCOMB-NEXT:       Symbol: bbb (2)
+# NOCOMB-NEXT:       Addend: 0x0
+# NOCOMB-NEXT:     }
+# NOCOMB-NEXT:     Relocation {
+# NOCOMB-NEXT:       Offset: 0x2018
+# NOCOMB-NEXT:       Type: R_X86_64_64
+# NOCOMB-NEXT:       Symbol: aaa (1)
+# NOCOMB-NEXT:       Addend: 0x0
+# NOCOMB-NEXT:     }
+# NOCOMB-NEXT:     Relocation {
+# NOCOMB-NEXT:       Offset: 0x2020
+# NOCOMB-NEXT:       Type: R_X86_64_64
+# NOCOMB-NEXT:       Symbol: ddd (4)
+# NOCOMB-NEXT:       Addend: 0x0
+# NOCOMB-NEXT:     }
+# NOCOMB-NEXT:   }
+# NOCOMB-NEXT:  ]
+# NOCOMB:      DynamicSection [
+# NOCOMB-NEXT:   Tag
+# NOCOMB-NOT:    RELACOUNT
+
+.data
+ .quad aaa
+ .quad ccc
+ .quad bbb
+ .quad aaa
+ .quad ddd
diff --git a/lld/test/ELF/gotpcrelx.s b/lld/test/ELF/gotpcrelx.s
index 169a479..3f21c81 100644
--- a/lld/test/ELF/gotpcrelx.s
+++ b/lld/test/ELF/gotpcrelx.s
@@ -24,7 +24,7 @@ movl bar@GOTPCREL(%rip), %eax
 
 // CHECK:      Relocations [
 // CHECK-NEXT:   Section ({{.*}}) .rela.dyn {
-// CHECK-NEXT:     0x2090 R_X86_64_GLOB_DAT foo 0x0
 // CHECK-NEXT:     0x2098 R_X86_64_GLOB_DAT bar 0x0
+// CHECK-NEXT:     0x2090 R_X86_64_GLOB_DAT foo 0x0
 // CHECK-NEXT:   }
 // CHECK-NEXT: ]
diff --git a/lld/test/ELF/i386-tls-ie-shared.s b/lld/test/ELF/i386-tls-ie-shared.s
index c45baab..a2c25e2 100644
--- a/lld/test/ELF/i386-tls-ie-shared.s
+++ b/lld/test/ELF/i386-tls-ie-shared.s
@@ -24,16 +24,16 @@
 // GOTRELSHARED:      Relocations [
 // GOTRELSHARED-NEXT:   Section ({{.*}}) .rel.dyn {
 // GOTRELSHARED-NEXT:     0x2002 R_386_RELATIVE - 0x0
-// GOTRELSHARED-NEXT:     0x1050 R_386_TLS_TPOFF tlslocal0 0x0
 // GOTRELSHARED-NEXT:     0x200A R_386_RELATIVE - 0x0
 // GOTRELSHARED-NEXT:     0x2013 R_386_RELATIVE - 0x0
 // GOTRELSHARED-NEXT:     0x201C R_386_RELATIVE - 0x0
-// GOTRELSHARED-NEXT:     0x1054 R_386_TLS_TPOFF tlslocal1 0x0
 // GOTRELSHARED-NEXT:     0x2024 R_386_RELATIVE - 0x0
 // GOTRELSHARED-NEXT:     0x202D R_386_RELATIVE - 0x0
 // GOTRELSHARED-NEXT:     0x2036 R_386_RELATIVE - 0x0
-// GOTRELSHARED-NEXT:     0x1058 R_386_TLS_TPOFF tlsshared0 0x0
 // GOTRELSHARED-NEXT:     0x203F R_386_RELATIVE - 0x0
+// GOTRELSHARED-NEXT:     0x1050 R_386_TLS_TPOFF tlslocal0 0x0
+// GOTRELSHARED-NEXT:     0x1054 R_386_TLS_TPOFF tlslocal1 0x0
+// GOTRELSHARED-NEXT:     0x1058 R_386_TLS_TPOFF tlsshared0 0x0
 // GOTRELSHARED-NEXT:     0x105C R_386_TLS_TPOFF tlsshared1 0x0
 // GOTRELSHARED-NEXT:   }
 // GOTRELSHARED-NEXT: ]
diff --git a/lld/test/ELF/mips-32.s b/lld/test/ELF/mips-32.s
index 6622aea..7875c48 100644
--- a/lld/test/ELF/mips-32.s
+++ b/lld/test/ELF/mips-32.s
@@ -47,8 +47,8 @@ v2:
 
 # REL:      Relocations [
 # REL-NEXT:   Section (7) .rel.dyn {
-# REL-NEXT:     0x30004 R_MIPS_REL32 v2 0x0
 # REL-NEXT:     0x30008 R_MIPS_REL32 - 0x0
+# REL-NEXT:     0x30004 R_MIPS_REL32 v2 0x0
 # REL-NEXT:   }
 # REL-NEXT: ]
 
diff --git a/lld/test/ELF/mips-64.s b/lld/test/ELF/mips-64.s
index d4a8df3..3d5c16a 100644
--- a/lld/test/ELF/mips-64.s
+++ b/lld/test/ELF/mips-64.s
@@ -36,8 +36,8 @@ v2:
 
 # CHECK:      Relocations [
 # CHECK-NEXT:   Section (7) .rela.dyn {
-# CHECK-NEXT:     0x30008 R_MIPS_REL32/R_MIPS_64/R_MIPS_NONE v2 0x8
 # CHECK-NEXT:     0x30010 R_MIPS_REL32/R_MIPS_64/R_MIPS_NONE - 0x30000
+# CHECK-NEXT:     0x30008 R_MIPS_REL32/R_MIPS_64/R_MIPS_NONE v2 0x8
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
diff --git a/lld/test/ELF/tls-dynamic-i686.s b/lld/test/ELF/tls-dynamic-i686.s
index 5d17d7c..4db6278 100644
--- a/lld/test/ELF/tls-dynamic-i686.s
+++ b/lld/test/ELF/tls-dynamic-i686.s
@@ -67,12 +67,12 @@ addl tls1@gotntpoff(%ebx),%eax
 
 // CHECK: Relocations [
 // CHECK:      Section ({{.+}}) .rel.dyn {
+// CHECK-NEXT: 0x2078 R_386_TLS_DTPMOD32 - 0x0
 // CHECK-NEXT: 0x2068 R_386_TLS_DTPMOD32 tls0 0x0
 // CHECK-NEXT: 0x206C R_386_TLS_DTPOFF32 tls0 0x0
+// CHECK-NEXT: 0x2080 R_386_TLS_TPOFF tls0 0x0
 // CHECK-NEXT: 0x2070 R_386_TLS_DTPMOD32 tls1 0x0
 // CHECK-NEXT: 0x2074 R_386_TLS_DTPOFF32 tls1 0x0
-// CHECK-NEXT: 0x2078 R_386_TLS_DTPMOD32 - 0x0
-// CHECK-NEXT: 0x2080 R_386_TLS_TPOFF tls0 0x0
 // CHECK-NEXT: 0x2084 R_386_TLS_TPOFF tls1 0x0
 // CHECK-NEXT: }
 
diff --git a/lld/test/ELF/tls-got.s b/lld/test/ELF/tls-got.s
index aa02451..f36d94e 100644
--- a/lld/test/ELF/tls-got.s
+++ b/lld/test/ELF/tls-got.s
@@ -24,8 +24,8 @@
 
 // CHECK:      Relocations [
 // CHECK-NEXT:   Section (4) .rela.dyn {
-// CHECK-NEXT:     [[ADDR]] R_X86_64_TPOFF64 tls1 0x0
 // CHECK-NEXT:     0x120B8 R_X86_64_TPOFF64 tls0 0x0
+// CHECK-NEXT:     [[ADDR]] R_X86_64_TPOFF64 tls1 0x0
 // CHECK-NEXT:   }
 // CHECK-NEXT: ]
 
diff --git a/lld/test/ELF/tls-i686.s b/lld/test/ELF/tls-i686.s
index 6395dde..e0a1007 100644
--- a/lld/test/ELF/tls-i686.s
+++ b/lld/test/ELF/tls-i686.s
@@ -62,8 +62,8 @@ _start:
 // RELOCSHARED:      Relocations [
 // RELOCSHARED-NEXT: Section (4) .rel.dyn {
 // RELOCSHARED-NEXT:   0x2001 R_386_TLS_TPOFF32 var 0x0
-// RELOCSHARED-NEXT:   0x200F R_386_TLS_TPOFF32 var1 0x0
 // RELOCSHARED-NEXT:   0x2025 R_386_TLS_TPOFF var 0x0
+// RELOCSHARED-NEXT:   0x200F R_386_TLS_TPOFF32 var1 0x0
 // RELOCSHARED-NEXT:   0x2032 R_386_TLS_TPOFF var1 0x0
 // RELOCSHARED-NEXT:  }
 // RELOCSHARED-NEXT: ]