[ELF] - Implemented -z combrelocs/nocombreloc.

[grimar]

Summary

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

[ruiu]

There are two ways of doing this. One way is, as you did, to sort symbols before writing it to the mmap'ed output. The other way is to write relocations to the buffer and sort the buffer as an array of RelTy. I think the latter is more efficient than the former because of better locality. Did you consider doing that way?

[grimar]

• Addressed Rui's comment.

[grimar]

In D19528#413335, @ruiu wrote:

There are two ways of doing this. One way is, as you did, to sort symbols before writing it to the mmap'ed output. The other way is to write relocations to the buffer and sort the buffer as an array of RelTy. I think the latter is more efficient than the former because of better locality. Did you consider doing that way?

I did, but idea of sorting something that was already written did not look clean for me, I did not think
about possible perfomance win though. So, probably you're right, updated the patch.

[hjl.tools]

I have found -z nocombreloc useful to debug ld and ld.so.

[grimar]

In D19528#413580, @hjl.tools wrote:

I have found -z nocombreloc useful to debug ld and ld.so.

This can be really one-line-easy to add in lld, if restoring the original
order of relocations can be useful for something.
But again, gold does ignore that option, so it seems usecase
is very specific.

[hjl.tools]

In D19528#413590, @grimar wrote:

In D19528#413580, @hjl.tools wrote:

I have found -z nocombreloc useful to debug ld and ld.so.

This can be really one-line-easy to add in lld, if restoring the original
order of relocations can be useful for something.
But again, gold does ignore that option, so it seems usecase
is very specific.

Well, gold can't build ld.so on Linux.

[grimar]

• Added -z nocombreloc support.

[grimar]

In D19528#413617, @hjl.tools wrote:

In D19528#413590, @grimar wrote:

In D19528#413580, @hjl.tools wrote:

I have found -z nocombreloc useful to debug ld and ld.so.

This can be really one-line-easy to add in lld, if restoring the original
order of relocations can be useful for something.
But again, gold does ignore that option, so it seems usecase
is very specific.

Well, gold can't build ld.so on Linux.

So just in case, I added support of -z nocombreloc, since it anyways trivial and short in code,

[ruiu]

It is generally looking good.

ELF/Driver.cpp

354 ↗

(On Diff #55234)

Let's name ZCombreloc as this is a one-word option (if it were -z no-comb-reloc, then I'd name it ZCombReloc). Maybe we want to change ZExecStack to ZExecstack too.

ELF/OutputSections.cpp

306 ↗

(On Diff #55234)

SHF_ALLOC), Sort(Sort) {

323–324 ↗

(On Diff #55234)

Please use uint8_t instead of unsigned char.

329 ↗

(On Diff #55234)

Remove else after return.

331 ↗

(On Diff #55234)

Ditto.

333–334 ↗

(On Diff #55234)

I'd use X and Y (or whatever) rather than IdxA and IdxB because they have very narrow scopes.

341–342 ↗

(On Diff #55234)

You don't need these temporary variables because you can use A.r_offset and B.r_offset directly.

364–365 ↗

(On Diff #55234)

Let's invert this condition and add comment before if about -z combreloc option.

// Sort relocations by r_offset, breaking ties with other conditions.
// Doing this does not change the semantics nor the file format, but
// some dynamic linker can load executables/DSOs faster when the
// relocation table is sorted. The fact that we have sorted relocations 
// is recorded using DT_RELACOUNT tag.
// http://people.redhat.com/jakub/prelink.pdf

643–644 ↗

(On Diff #55234)

Swap the two ifs so that we don't call getRelativeCount if the feature is disabled.

Also, does it make sense to not emit DT_RELACOUNT if there's no relative relocations?

ELF/OutputSections.h

232 ↗

(On Diff #55234)

I wouldn't use default argument lightly because it is virtually defining two different functions, with and without the parameter. I prefer passing the argument explicitly.

244 ↗

(On Diff #55234)

NumRelativeRels may be better.

ELF/Writer.cpp

132 ↗

(On Diff #55234)

I wouldn't define this because it is used only once.

[grimar]

• Addressed review comments.

ELF/Driver.cpp

354 ↗

(On Diff #55234)

Done.

ELF/OutputSections.cpp

306 ↗

(On Diff #55234)

Done, but I dont sure I like how it looks after clang-format.

323–324 ↗

(On Diff #55234)

Done.

329 ↗

(On Diff #55234)

Done.

331 ↗

(On Diff #55234)

Done.

333–334 ↗

(On Diff #55234)

Done.

341–342 ↗

(On Diff #55234)

Done.

364–365 ↗

(On Diff #55234)

Done, but:

1. "The fact that we have sorted relocations is recorded using DT_RELACOUNT tag." was not quite correct, I removed it. DT_RELACOUNT just keeps amount of Relative relocations at start of rela.dyn. We can have zero of such relocations and DT_RELACOUNT entry will absent. But relocations will still be sorted. That how golds works, and it seems reasonable: there is no point in zero filled tag about relative relocations, we will still have some boost after sorting others one.
2. Changed link to Ian Lance Tailor notes about it.

643–644 ↗

(On Diff #55234)

DT_RELACOUNT == 0 just wastes file space and does not affect anything I think.
It looks like excessive job for lld to generate it and for dynamic linker to proccess the
empty record.
gold do the same, btw.

ELF/OutputSections.h

232 ↗

(On Diff #55234)

Done.

244 ↗

(On Diff #55234)

Done.

ELF/Writer.cpp

132 ↗

(On Diff #55234)

Done.

[grimar]

Below are first benchmark result I got:

used release shared build of clang:
-DCMAKE_BUILD_TYPE=Release -DLLVM_BUILD_LLVM_DYLIB=true -DBUILD_SHARED_LIBS=true
OS: Ubuntu 16.04 LTS 64bit.
Each time I run test 5 times and selected average by total startup time result:

// 1. With this full patch:
umb@ubuntu:~/umb/LLVM/self-host-my-shared/bin$ LD_DEBUG=statistics ./clang

42269:	
42269:	runtime linker statistics:
42269:	  total startup time in dynamic loader: 102686501 cycles
42269:		    time needed for relocation: 78691443 cycles (76.6%)
42269:	                 number of relocations: 15077
42269:	      number of relocations from cache: 14659
42269:	        number of relative relocations: 136769
42269:		   time needed to load objects: 22087834 cycles (21.5%)

// 2. Without this patch:
umb@ubuntu:~/umb/LLVM/self-host-orig-shared/bin$ LD_DEBUG=statistics ./clang

42265:	
42265:	runtime linker statistics:
42265:	  total startup time in dynamic loader: 151284557 cycles
42265:		    time needed for relocation: 127451126 cycles (84.2%)
42265:	                 number of relocations: 27492
42265:	      number of relocations from cache: 2244
42265:	        number of relative relocations: 2020
42265:		   time needed to load objects: 21858213 cycles (14.4%)

Amount of startup time cycles wo/patch patch is 1.47x in compare with w/patch.
Time needed for relocations is 1.61x.

// 3. With this patch, but do not set DT_RELACOUNT tag:
umb@ubuntu:~/umb/LLVM/self-hosting-notag/bin$ LD_DEBUG=statistics ./clang

101488:	
101488:	runtime linker statistics:
101488:	  total startup time in dynamic loader: 111007425 cycles
101488:		    time needed for relocation: 87371019 cycles (78.7%)
101488:	                 number of relocations: 15077
101488:	      number of relocations from cache: 14659
101488:	        number of relative relocations: 2020
101488:		   time needed to load objects: 21857215 cycles (19.6%)

~8% more startup cycles than (1).
~11% more relocation time cycles than (1).

Now I am going to test static -pie build.

[grimar]

In D19528#416734, @grimar wrote:

Now I am going to test static -pie build.

And I was not able to perform this test. Self-hosting with -pie configuration fails because llvm-tblgen segfaults (without my patch).
Full configuration line: -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/home/umb/umb/LLVM/build/bin/clang -DCMAKE_CXX_COMPILER=/home/umb/umb/LLVM/build/bin/clang++ -DLLVM_PARALLEL_COMPILE_JOBS=8 -DLLVM_ENABLE_THREADS=true -DCMAKE_CXX_FLAGS="-fuse-ld=lld -pie" -DCMAKE_C_FLAGS="-fuse-ld=lld -pie"

[169/2657 0.0/sec] Building Attributes.inc...
FAILED: include/llvm/IR/Attributes.inc.tmp 
cd /home/umb/umb/LLVM/no-tag-static/include/llvm/IR && /home/umb/umb/LLVM/no-tag-static/bin/llvm-tblgen -gen-attrs -I /home/umb/umb/LLVM/llvm/include/llvm/IR -I /home/umb/umb/LLVM/llvm/lib/Target -I /home/umb/umb/LLVM/llvm/include /home/umb/umb/LLVM/llvm/include/llvm/IR/Attributes.td -o /home/umb/umb/LLVM/no-tag-static/include/llvm/IR/Attributes.inc.tmp
Segmentation fault (core dumped)

Not sure, did anybody try -pie selfhosting before ?

But anyways previous benchmark results are probably enough for now to prove that patch is useful as is. Thoughts ?

[• rafael]

Please do simplify the patch to first not set any new DT_ and sort only by offset. Lets benchmark just that first.

ELF/Writer.cpp

168 ↗

(On Diff #55393)

Why can't you sort this? It shouldn't hurt when being lazy and it should help otherwise.

[grimar]

In D19528#422386, @rafael wrote:

Please do simplify the patch to first not set any new DT_ and sort only by offset. Lets benchmark just that first.

Ok, will try tomorrow.

ELF/Writer.cpp

168 ↗

(On Diff #55393)

Good point.

[grimar]

In D19528#422386, @rafael wrote:

Please do simplify the patch to first not set any new DT_ and sort only by offset. Lets benchmark just that first.

I did that (simplified version I used is here: D20013) and got no any perfomance boost after that at all
(or very minor what I believe is just a computing error):

Middle from 5 runs is shown.
Without patch:

umb@ubuntu:~/umb/LLVM/self-hosting/bin$ LD_DEBUG=statistics ./clang
     46693:	
     46693:	runtime linker statistics:
     46693:	  total startup time in dynamic loader: 193739180 cycles
     46693:		    time needed for relocation: 166734504 cycles (86.0%)
     46693:	                 number of relocations: 27736
     46693:	      number of relocations from cache: 2247
     46693:	        number of relative relocations: 2020
     46693:		   time needed to load objects: 24664951 cycles (12.7%)
clang-3.9: error: no input files
     46693:	
     46693:	runtime linker statistics:
     46693:	           final number of relocations: 28487
     46693:	final number of relocations from cache: 2247

With patch (no tag, sort by offset).

umb@ubuntu:~/umb/LLVM/selfhost-reduced/bin$ LD_DEBUG=statistics ./clang
     46666:	
     46666:	runtime linker statistics:
     46666:	  total startup time in dynamic loader: 188386979 cycles
     46666:		    time needed for relocation: 161439636 cycles (85.6%)
     46666:	                 number of relocations: 27736
     46666:	      number of relocations from cache: 2247
     46666:	        number of relative relocations: 2020
     46666:		   time needed to load objects: 24821139 cycles (13.1%)
clang-3.9: error: no input files
     46666:	
     46666:	runtime linker statistics:
     46666:	           final number of relocations: 28487
     46666:	final number of relocations from cache: 2247

I think results are expected as symbols are not grouped together, what
looks to be the main condition for optimization to work.

[• rafael]

I will try running benchmarks on a few variations of this.

[• rafael]

What version is this based on? I can't get it to apply cleanly.

[• rafael]

I was able to manually apply it.

What I did was:

• build clang with shared libraries.
• time with sudo schedtool -F -p 99 -a 0x4 -e perf stat -r 10 ./bin/clang
• build the patched version of lld
• delete bin/clang-3.9 and lib/*.so
• link again
• time the result

What I got was

• trunk: 0.059005660
• sort on RELATIVE, Symbol, offset, type: 0.040090757
• sort on Symbol, offset, type: 0.042367124
• sort on offset, type: 0.059119353
• sort on RELATIVE, Symbol, offset: 0.040131764
• sort on RELATIVE, Symbol: 0.040396584
• sort on RELATIVE: 0.058322444
• sort on Symbol: 0.039886032

So it looks like the only thing that makes a difference is the symbol.

BTW, one cannot sort .rel.plt, it would be nice to document why.
I think it is better to use stable_sort to be sure we have a
deterministic output without checking fields that don't make a
difference.

So a change sorting only by symbol with stable sort LGTM. Please make
sure you are not computing the number of relative rolocations or
setting any DT_*.

The partial apply that I used for benchmarking was.

Cheers,
Rafael

• t.diff3 KBDownload

[grimar]

I was able to manually apply it.

What I did was:

• build clang with shared libraries.
• time with

>sudo schedtool -F -p 99 -a 0x4 -e perf stat -r 10 ./bin/clang

• build the patched version of lld
• delete bin/clang-3.9 and lib/*.so
• link again
• time the result

What I got was

• trunk: 0.059005660
• sort on RELATIVE, Symbol, offset, type: 0.040090757
• sort on Symbol, offset, type: 0.042367124
• sort on offset, type: 0.059119353
• sort on RELATIVE, Symbol, offset: 0.040131764
• sort on RELATIVE, Symbol: 0.040396584
• sort on RELATIVE: 0.058322444
• sort on Symbol: 0.039886032

So it looks like the only thing that makes a difference is the symbol.

BTW, one cannot sort .rel.plt, it would be nice to document why.
I think it is better to use stable_sort to be sure we have a
deterministic output without checking fields that don't make a
difference.

So a change sorting only by symbol with stable sort LGTM. Please make
sure you are not computing the number of relative rolocations or
setting any DT_*.

The partial apply that I used for benchmarking was.

I'll update the patch a bit later then for final review.

At the same time I got 10% difference in startup cycles
when compared with DT_* vs without: http://reviews.llvm.org/D19528#416734
Do you think that was an computing error ?

[grimar]

• Sort only by symbols, using stable_sort.
• Do not create any DT_entries (I am still that that reduced startup cycles amount by 10%, so going to introduce another patch after landing this and after retesting the perfomance results I got before).

[grimar]

In D19528#423828, @rafael wrote:

BTW, one cannot sort .rel.plt, it would be nice to document why.

I also noticed that: when I sort the .rel.plt then produced lld linked binaries are broken (segfaults on startup,
not sure all of, but at least some of them do). Not sure I have any explanation for that now.

[• rafael]

LGTM

[grimar]

In D19528#425698, @grimar wrote:

• Sort only by symbols, using stable_sort.
• Do not create any DT_entries (I am sure that that reduced startup cycles amount by 10%, so going to introduce another patch after landing this and after retesting the perfomance results I got before).

I retested case when we are creating DT_RELACOUNT vs case when we are not (what is currently commited). Tried many times,
but it seems that difference is just a calcualtion error.
I am not sure what caused 10% difference I observed before, currently I have no reproduce for that anymore.

I tried
sudo schedtool -F -p 99 -a 0x1 -e perf stat -r 1000 ./clang
as well as just LD_DEBUG=statistics ./clang many times

Numbers are about the same in average.

Changes I tested today were:

patch.patch86 KBDownload

lld/trunk/ELF/Config.h

struct Configuration {
   bool StripAll;
   bool StripDebug;
   bool SysvHash = true;
   bool Threads;
   bool Trace;
   bool Verbose;
   bool VersionScript = false;
   bool WarnCommon;
+  bool ZCombreloc;
   bool ZExecStack;
   bool ZNodelete;
   bool ZNow;
   bool ZOrigin;
   bool ZRelro;
   BuildIdKind BuildId = BuildIdKind::None;
   ELFKind EKind = ELFNoneKind;
   uint16_t EMachine = llvm::ELF::EM_NONE;

lld/trunk/ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->Optimize = getInteger(Args, OPT_O, 1);
   Config->LtoO = getInteger(Args, OPT_lto_O, 2);
   if (Config->LtoO > 3)
     error("invalid optimization level for LTO: " + getString(Args, OPT_lto_O));
   Config->LtoJobs = getInteger(Args, OPT_lto_jobs, 1);
   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");
   Config->ZOrigin = hasZOption(Args, "origin");
   Config->ZRelro = !hasZOption(Args, "norelro");
 
   if (Config->Relocatable)
     Config->StripAll = false;

lld/trunk/ELF/OutputSections.h

 
 template <class ELFT>
 class RelocationSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   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;
   void writeTo(uint8_t *Buf) override;
   bool hasRelocs() const { return !Relocs.empty(); }
 
   bool Static = false;
 
 private:
+  bool Sort;
   std::vector<DynamicReloc<ELFT>> Relocs;
 };
 
 template <class ELFT>
 class OutputSection final : public OutputSectionBase<ELFT> {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;

lld/trunk/ELF/OutputSections.cpp

 }
 
 template <class ELFT> void PltSection<ELFT>::finalize() {
   this->Header.sh_size =
       Target->PltZeroSize + Entries.size() * Target->PltEntrySize;
 }
 
 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);
 }
 
 template <class ELFT>
 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);
     SymbolBody *Sym = Rel.Sym;
 
     if (Config->Rela)
       P->r_addend = Rel.UseSymVA ? Sym->getVA<ELFT>(Rel.Addend) : Rel.Addend;
     P->r_offset = Rel.OffsetInSec + Rel.OffsetSec->getVA();
     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() {
   return this->Header.sh_entsize * Relocs.size();
 }
 
 template <class ELFT> void RelocationSection<ELFT>::finalize() {
   this->Header.sh_link = Static ? Out<ELFT>::SymTab->SectionIndex

lld/trunk/ELF/Writer.cpp

template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
   typedef typename ELFT::Ehdr Elf_Ehdr;
 
   // Create singleton output sections.
   DynamicSection<ELFT> Dynamic(*Symtab);
   EhFrameHeader<ELFT> EhFrameHdr;
   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);
   VersionTableSection<ELFT> VerSym;
   VersionNeedSection<ELFT> VerNeed;
 
   OutputSectionBase<ELFT> ElfHeader("", 0, SHF_ALLOC);
   ElfHeader.setSize(sizeof(Elf_Ehdr));
template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
 
   if (Config->GnuHash)
     GnuHashTab.reset(new GnuHashTableSection<ELFT>);
   if (Config->SysvHash)
     HashTab.reset(new HashTableSection<ELFT>);
   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));
     SymTabSec.reset(new SymbolTableSection<ELFT>(*Symtab, *StrTab));
   }
   if (Config->EMachine == EM_MIPS && !Config->Shared) {
     // This is a MIPS specific section to hold a space within the data segment
     // of executable file which is pointed to by the DT_MIPS_RLD_MAP entry.

lld/trunk/test/ELF/aarch64-abs64-dyn.s

bar:
         .data
         .xword foo
         .xword bar
 
 // RUN: ld.lld -shared -o %t.so %t.o
 // 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 [
 // CHECK:        Symbol {
 // CHECK:          Name: bar
 // CHECK-NEXT:     Value: [[BAR_ADDR]]

lld/trunk/test/ELF/aarch64-tls-ie.s

 #RELOC-NEXT:   Size: 16
 #RELOC-NEXT:   Link: 0
 #RELOC-NEXT:   Info: 0
 #RELOC-NEXT:   AddressAlignment: 8
 #RELOC-NEXT:   EntrySize: 0
 #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:]
 
 # Page(0x120B0) - Page(0x11000) = 0x1000 = 4096
 # 0x120B0 & 0xff8 = 0xB0 = 176
 # Page(0x120B8) - Page(0x11000) = 0x1000 = 4096
 # 0x120B8 & 0xff8 = 0xB8 = 184
 #CHECK: Disassembly of section .text:

lld/trunk/test/ELF/combrelocs.s

+# 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

lld/trunk/test/ELF/gotpcrelx.s

 // CHECK-NEXT: Flags [
 // CHECK-NEXT:   SHF_ALLOC
 // CHECK-NEXT:   SHF_WRITE
 // CHECK-NEXT: ]
 // CHECK-NEXT: Address: 0x2090
 
 // 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: ]

lld/trunk/test/ELF/i386-tls-ie-shared.s

 // GOTRELSHARED-NEXT:   Link: 0
 // GOTRELSHARED-NEXT:   Info: 0
 // GOTRELSHARED-NEXT:   AddressAlignment: 4
 // GOTRELSHARED-NEXT:   EntrySize: 0
 // GOTRELSHARED-NEXT: }
 // 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: ]
 
 // DISASMSHARED:       Disassembly of section test:
 // DISASMSHARED-NEXT:  _start:
 // (.got)[0] = 0x2050 = 8272
 // (.got)[1] = 0x2054 = 8276

lld/trunk/test/ELF/mips-32.s

 #                         ^-- v2+4 ^-- v1
 
 # SYM: SYMBOL TABLE:
 # SYM: 00030000 l       .data           00000004 v1
 # SYM: 00030004 g       .data           00000008 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: ]
 
 # REL: DynamicSection [
 # REL:   Tag        Type                 Name/Value
 # REL:   0x00000012 RELSZ                16 (bytes)
 # REL:   0x00000013 RELENT               8 (bytes)
 

lld/trunk/test/ELF/mips-64.s

 #                 ^-- v1
 
 # SYM: SYMBOL TABLE:
 # SYM: 00030000 l       .data           00000004 v1
 # SYM: 00030008 g       .data           00000008 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: ]
 
 # CHECK: DynamicSection [
 # CHECK:   Tag        Type     Name/Value
 # CHECK:   0x0000000000000008 RELASZ    48 (bytes)
 # CHECK:   0x0000000000000009 RELAENT   24 (bytes)
 

lld/trunk/test/ELF/tls-dynamic-i686.s

 // CHECK-NEXT: Size: 32
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 4
 // CHECK-NEXT: EntrySize: 0
 
 // 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: }
 
 // DIS:      Disassembly of section .text:
 // DIS-NEXT: _start:
 // General dynamic model:
 // -32 and -24 are first and second GOT entries offsets.
 // Each one is a pair of records.

lld/trunk/test/ELF/tls-got.s

 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 8
 // CHECK-NEXT: EntrySize: 0
 // CHECK-NEXT: }
 
 // 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: ]
 
 //0x11000 + 4249 + 7 = 0x120B0
 //0x1100A + 4247 + 7 = 0x120B8
 //0x11014 + 4237 + 7 = 0x120B8
 //DISASM:      Disassembly of section .text:
 //DISASM-NEXT: main:

lld/trunk/test/ELF/tls-i686.s

 // DISSHARED-NEXT: 201c: 65 8b 0d 00 00 00 00  movl %gs:0, %ecx
 // DISSHARED-NEXT: 2023: 8d 81 00 00 00 00     leal (%ecx), %eax
 // DISSHARED-NEXT: 2029: 65 8b 0d 00 00 00 00  movl %gs:0, %ecx
 // DISSHARED-NEXT: 2030: 8d 81 00 00 00 00     leal (%ecx), %eax
 
 // 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: ]