[ELF] - Implemented --symbol-ordering-file option.

[grimar]

Summary

This is close to D25766, but uses list of symbols instead of list of sections.

Numbers I got benchmarking clang -help were:
For 1000 runs of ordered and unordered build amount of pagefaults: 636 vs 641 +- 0.01%.
Time was (from real HW) 0.124324230 vs 0.127807916 (+- 0.2%), so it is 2.8% boost.

Used symbols files is https://justpaste.it/zwm4

[grimar]

• Refactored.
• Added testcase showing ability to sort sections with the same name (.text).

[ruiu]

Well, again, you really need to run a long sequence of computations to get meaningful numbers for benchmark. clang -help isn't useful for that purpose.

[davide]

In D26130#583948, @ruiu wrote:

Well, again, you really need to run a long sequence of computations to get meaningful numbers for benchmark. clang -help isn't useful for that purpose.

Agree (as already pointed out in the other thread review). I discussed this a bit with Rafael and I see his point of view, i.e. clang -help is definitely a sanity check, and the number of page faults being decreased is a good thing, but I'd really love this to be tested on a startup-time sensitive application.
I mentioned browsers, in particular Firefox, because the Mozilla people spent quite a bit of time thinking about the problem, so you should be able to reuse all their infrastructure (tests etc..). Firefox should link out-the-box with lld, and if it doesn't .. well there's more work to to there =)

[grimar]

In D26130#583948, @ruiu wrote:

Well, again, you really need to run a long sequence of computations to get meaningful numbers for benchmark. clang -help isn't useful for that purpose.

Yes, Rui, please don't think I forgot about that opinion :) clang -help looks good because of very stable results. As I pointed I observe the same amount of faults for the same binary on 2 different PC. So it defenetely (IMO) proves that patch can be used to reduce them during startup.

In D26130#583961, @davide wrote:

In D26130#583948, @ruiu wrote:

Well, again, you really need to run a long sequence of computations to get meaningful numbers for benchmark. clang -help isn't useful for that purpose.

Agree (as already pointed out in the other thread review). I discussed this a bit with Rafael and I see his point of view, i.e. clang -help is definitely a sanity check, and the number of page faults being decreased is a good thing, but I'd really love this to be tested on a startup-time sensitive application.
I mentioned browsers, in particular Firefox, because the Mozilla people spent quite a bit of time thinking about the problem, so you should be able to reuse all their infrastructure (tests etc..). Firefox should link out-the-box with lld, and if it doesn't .. well there's more work to to there =)

I did not yet try firefox with this patch. But as I wrote in another thread, I was unable to obtain a boost using --sections-ordering-file on clang and firefox previously. Though sections file for firefox produced by icegrind was 5 megabytes in size, what is much more than 300 entries that works with this patch.
So the noticable result using --symbol-ordering-file and Rafael's method of generating it is probably a step forward that was worth to share.

Will try to test firefox using this patch.

(about linking firefox with lld. When last time I did that, it produced next error for me during launch:

umb@ubuntu:~/firefox/clean/mozilla-central$ /home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/dist/bin/firefox -no-remote -profile /home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/tmp/scratch0
XPCOMGlueLoad error for file /home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/dist/bin/libxul.so:
/home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/dist/bin/libxul.so: undefined symbol: gtk_main_do_event
Couldn't load XPCOM.

so I had to link firefox with gold and then relink libxul.so with lld. That should have being fine I think since that is the single core library of firefox and sections file was targeted for it.
And anyways latest tests I performed on vanilla gold to check the option itself, and result was the same).

[• rafael]

Just some quick observations while building the patch :-)

ELF/SymbolListFile.cpp

65 ↗

(On Diff #76396)

It is not entirely clear you want the ScriptParser infrastructure. For example, do we have to handle quotes?

I would probably make this format dead simple. One symbol per line, symbols with newlines are not supported.

ELF/Writer.cpp

679 ↗

(On Diff #76396)

This is crazy inefficient.

You probably want to make SymbolOrderingFile a DenseMap from CachedStringRef to unsigned.

test/ELF/symbol-ordering-file.s

9 ↗

(On Diff #76396)

Changing .text to .foo should make this easier to read as .foo doesn't have an implicit alignment.

[grimar]

ELF/Writer.cpp

679 ↗

(On Diff #76396)

Yeah.. that was stupid from my side. I am going to address this one and other comments tomorrow.

[grimar]

• Addressed review comments.

ELF/SymbolListFile.cpp

65 ↗

(On Diff #76396)

I expected this file can have comments like --sections--list-file.
Not sure that more parsing code here is better than reusing ScriptParser. I did that though.

test/ELF/symbol-ordering-file.s

9 ↗

(On Diff #76396)

linker does not concatinate .foo into single section like .text.* :(
So I had to use .text

[grimar]

• Simplified.

[davide]

Some comments inline.

ELF/SymbolListFile.cpp

64–65 ↗

(On Diff #76827)

Ehm, splitting a file by line is something that can be probably useful outside of lld, so I propose this to live in ADT/StringRef (or something like that).

78–79 ↗

(On Diff #76827)

Unless I'm mistaken, you can probably fold Arr.

ELF/Writer.cpp

644 ↗

(On Diff #76827)

nit: using the list
nit2: s/option//

646 ↗

(On Diff #76827)

I find the name sortSectionsByOrder a little confusing.

659–660 ↗

(On Diff #76827)

I prefer details about symbols not being exposed.

So, any reason why you can't use

template <class ELFT>
static StringRef getSymbolName(const elf::ObjectFile<ELFT> &File,
                               SymbolBody &Body) {

here?

669–670 ↗

(On Diff #76827)

This just duplicates the comment at the beginning of the function, so I'd either
a) make it more useful
b) remove it altogether

[davide]

test/ELF/symbol-ordering-file.s

9 ↗

(On Diff #76396)

Can't you just use multiple input files with two .foo sections?

[davide]

In D26130#584374, @grimar wrote:

In D26130#583948, @ruiu wrote:

Well, again, you really need to run a long sequence of computations to get meaningful numbers for benchmark. clang -help isn't useful for that purpose.

Yes, Rui, please don't think I forgot about that opinion :) clang -help looks good because of very stable results. As I pointed I observe the same amount of faults for the same binary on 2 different PC. So it defenetely (IMO) proves that patch can be used to reduce them during startup.

In D26130#583961, @davide wrote:

In D26130#583948, @ruiu wrote:

Well, again, you really need to run a long sequence of computations to get meaningful numbers for benchmark. clang -help isn't useful for that purpose.

Agree (as already pointed out in the other thread review). I discussed this a bit with Rafael and I see his point of view, i.e. clang -help is definitely a sanity check, and the number of page faults being decreased is a good thing, but I'd really love this to be tested on a startup-time sensitive application.
I mentioned browsers, in particular Firefox, because the Mozilla people spent quite a bit of time thinking about the problem, so you should be able to reuse all their infrastructure (tests etc..). Firefox should link out-the-box with lld, and if it doesn't .. well there's more work to to there =)

I did not yet try firefox with this patch. But as I wrote in another thread, I was unable to obtain a boost using --sections-ordering-file on clang and firefox previously. Though sections file for firefox produced by icegrind was 5 megabytes in size, what is much more than 300 entries that works with this patch.
So the noticable result using --symbol-ordering-file and Rafael's method of generating it is probably a step forward that was worth to share.

Will try to test firefox using this patch.

(about linking firefox with lld. When last time I did that, it produced next error for me during launch:

umb@ubuntu:~/firefox/clean/mozilla-central$ /home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/dist/bin/firefox -no-remote -profile /home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/tmp/scratch0
XPCOMGlueLoad error for file /home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/dist/bin/libxul.so:
/home/umb/firefox/clean/mozilla-central/obj-x86_64-pc-linux-gnu/dist/bin/libxul.so: undefined symbol: gtk_main_do_event
Couldn't load XPCOM.

so I had to link firefox with gold and then relink libxul.so with lld. That should have being fine I think since that is the single core library of firefox and sections file was targeted for it.
And anyways latest tests I performed on vanilla gold to check the option itself, and result was the same).

If lld mislinks firefox, we shouldn't silently ignore it and try to link with gold, but open a bug instead (and/or try to fix).

[grimar]

In D26130#587774, @davide wrote:

If lld mislinks firefox, we shouldn't silently ignore it and try to link with gold, but open a bug instead (and/or try to fix).

I think it is just an issue of their build system.
I found similar issues: https://bugzilla.mozilla.org/show_bug.cgi?id=1080654, https://bugzilla.mozilla.org/show_bug.cgi?id=1063359

widget/gtk/mozgtk/gtk3/moz.build has next lines:

if CONFIG['GCC_USE_GNU_LD']:
    no_as_needed = ['-Wl,--no-as-needed1']
    as_needed = ['-Wl,--as-needed']
else:
    no_as_needed = []
    as_needed = []

If I change the last two to have -Wl..., then build works fine for me.

test/ELF/symbol-ordering-file.s

9 ↗

(On Diff #76396)

I think reasonable minimum to show that sorting is performed according to order file is
at least 3 sections. So that would be main test file + 2 input files.

I find testcases that use additional inputs harder to read generally, so actually I would prefer current way
when testcase is just a two files in total.
My test has 5 sections what also allows to check spaces before/after symbol in ordering file,
doing that with .foo and multiple inputs would require 4 input files I think.

[grimar]

• Addressed review comments.

ELF/SymbolListFile.cpp

64–65 ↗

(On Diff #76827)

StringRef::split() can do this job, used it instead.

78–79 ↗

(On Diff #76827)

We don't use regexps in lld anymore. StringMatcher has a list of patterns,
them are unfolded.
So I think keeping SymbolOrderingFile as a DenseMap should be faster.

ELF/Writer.cpp

644 ↗

(On Diff #76827)

Done.

646 ↗

(On Diff #76827)

May be sortBySymbolsOrder ?

659–660 ↗

(On Diff #76827)

Done.

669–670 ↗

(On Diff #76827)

Removed.

[• rafael]

Please also add to the test to show that if a section has multiple symbols, we use the one with the lowest index in the order file.

ELF/SymbolListFile.cpp

66 ↗

(On Diff #77024)

I would probably just use 0 instead of 32. This will not be small in any interesting case.

ELF/Writer.cpp

668 ↗

(On Diff #77024)

In case two symbols point to the same section, we probably want the first one to win. This means that this should probably use the minimum.

[emaste]

If lld mislinks firefox, we shouldn't silently ignore it and try to link with gold, but open a bug instead (and/or try to fix).

A Firefox bug, it seems.

if CONFIG['GCC_USE_GNU_LD']:

It looks like Firefox uses this rather unfortunate test:

if test "$GNU_CC"; then
    if `$CC -print-prog-name=ld` -v 2>&1 | grep -c GNU >/dev/null; then
        GCC_USE_GNU_LD=1
    fi
fi

and there's been a history of issues detecting the linker type, e.g. https://bugzilla.mozilla.org/show_bug.cgi?id=1049510.

I suspect we could set this to 1 also for lld (at least, I think it's reasonable that lld will support ld.bfd options or behaviour that Firefox relies on). However, it seems like someone familiar with Firefox ought to audit all of the uses of GCC_USE_GNU_LD and replace them with tests on the actual functionality required.

[grimar]

• Addressed review comments.

ELF/SymbolListFile.cpp

66 ↗

(On Diff #77024)

Done.

ELF/Writer.cpp

668 ↗

(On Diff #77024)

Right. It used minimum when had one more "crazy" loop outsize, but after switching to DenseMap this logic gone accidentally. Fixed.

[• rafael]

LGTM by me, but please wait for a LGTM from Rui and Davide too.

Thanks for implementing this!

[ruiu]

ELF/SymbolListFile.cpp

60 ↗

(On Diff #77043)

This function should live in Driver.cpp as this has nothing to do with ScriptParser class.

ELF/Writer.cpp

659 ↗

(On Diff #77043)

I think we should iterate over Config->SymbolOrderingFile and use SymbolTable::find() instead of iterating over all symbols because the former should be much faster than the latter.

[grimar]

• Addressed review comments.

[grimar]

ELF/SymbolListFile.cpp

60 ↗

(On Diff #77043)

Done.

ELF/Writer.cpp

659 ↗

(On Diff #77043)

As Rafael already pointed out, there is no local symbols in symbol table.

[ruiu]

LGTM

[davide]

This looks good now. Thanks for your extreme patience addressing all my (ours) comments.

[grimar]

Cool ! Davide, Rafael, Rui, thank you guys for usefull comments and help with that !

lld/trunk/ELF/Config.h

 //===- Config.h -------------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_CONFIG_H
 #define LLD_ELF_CONFIG_H
 
+#include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ELF.h"
 
 #include <vector>
 
 namespace lld {
 namespace elf {

 
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   InputFile *FirstElf = nullptr;
   uint8_t OSABI = 0;
+  llvm::DenseMap<llvm::CachedHashStringRef, unsigned> SymbolOrderingFile;
   llvm::StringMap<uint64_t> SectionStartMap;
   llvm::StringRef DynamicLinker;
   llvm::StringRef Entry;
   llvm::StringRef Emulation;
   llvm::StringRef Fini;
   llvm::StringRef Init;
   llvm::StringRef LtoAAPipeline;
   llvm::StringRef LtoNewPmPasses;

lld/trunk/ELF/Driver.cpp

if (S == "alignment")
     return SortSectionPolicy::Alignment;
   if (S == "name")
     return SortSectionPolicy::Name;
   if (!S.empty())
     error("unknown --sort-section rule: " + S);
   return SortSectionPolicy::Default;
 }
 
+// Parse the --symbol-ordering-file argument. File has form:
+// symbolName1
+// [...]
+// symbolNameN
+static void parseSymbolOrderingList(MemoryBufferRef MB) {
+  unsigned I = 0;
+  SmallVector<StringRef, 0> Arr;
+  MB.getBuffer().split(Arr, '\n');
+  for (StringRef S : Arr)
+    Config->SymbolOrderingFile.insert({CachedHashStringRef(S.trim()), I++});
+}
+
 // Initializes Config members by the command line options.
 void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   for (auto *Arg : Args.filtered(OPT_L))
     Config->SearchPaths.push_back(Arg->getValue());
 
   std::vector<StringRef> RPaths;
   for (auto *Arg : Args.filtered(OPT_rpath))
     RPaths.push_back(Arg->getValue());
void LinkerDriver::readConfigs(opt::InputArgList &Args) {
 
   for (auto *Arg : Args.filtered(OPT_undefined))
     Config->Undefined.push_back(Arg->getValue());
 
   if (auto *Arg = Args.getLastArg(OPT_dynamic_list))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       parseDynamicList(*Buffer);
 
+  if (auto *Arg = Args.getLastArg(OPT_symbol_ordering_file))
+    if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
+      parseSymbolOrderingList(*Buffer);
+
   for (auto *Arg : Args.filtered(OPT_export_dynamic_symbol))
     Config->DynamicList.push_back(Arg->getValue());
 
   if (auto *Arg = Args.getLastArg(OPT_version_script))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       readVersionScript(*Buffer);
 }
 

lld/trunk/ELF/Options.td

 
 def start_lib: F<"start-lib">,
   HelpText<"Start a grouping of objects that should be treated as if they were together in an archive">;
 
 def strip_all: F<"strip-all">, HelpText<"Strip all symbols">;
 
 def strip_debug: F<"strip-debug">, HelpText<"Strip debugging information">;
 
+def symbol_ordering_file: S<"symbol-ordering-file">,
+  HelpText<"Layout sections in the order specified by symbol file">;
+
 def sysroot: J<"sysroot=">, HelpText<"Set the system root">;
 
 def target1_rel: F<"target1-rel">, HelpText<"Interpret R_ARM_TARGET1 as R_ARM_REL32">;
 
 def target1_abs: F<"target1-abs">, HelpText<"Interpret R_ARM_TARGET1 as R_ARM_ABS32">;
 
 def target2: J<"target2=">, MetaVarName<"<type>">, HelpText<"Interpret R_ARM_TARGET2 as <type>, where <type> is one of rel, abs, or got-rel.">;
 

lld/trunk/ELF/OutputSections.h

 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::uint uintX_t;
   OutputSection(StringRef Name, uint32_t Type, uintX_t Flags);
   void addSection(InputSectionData *C) override;
+  void sort(std::function<unsigned(InputSection<ELFT> *S)> Order);
   void sortInitFini();
   void sortCtorsDtors();
   void writeTo(uint8_t *Buf) override;
   void finalize() override;
   void assignOffsets() override;
   Kind getKind() const override { return Regular; }
   static bool classof(const OutputSectionBase *B) {
     return B->getKind() == Regular;

lld/trunk/ELF/OutputSections.cpp

 //===- OutputSections.cpp -------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "OutputSections.h"
 #include "Config.h"
 #include "EhFrame.h"
 #include "GdbIndex.h"
 #include "LinkerScript.h"
 #include "Memory.h"
 #include "Strings.h"
+#include "SymbolListFile.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Core/Parallel.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/SHA1.h"
template <class ELFT> void OutputSection<ELFT>::assignOffsets() {
   for (InputSection<ELFT> *S : Sections) {
     Off = alignTo(Off, S->Alignment);
     S->OutSecOff = Off;
     Off += S->getSize();
   }
   this->Size = Off;
 }
 
-// Sorts input sections by section name suffixes, so that .foo.N comes
-// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
-// We want to keep the original order if the priorities are the same
-// because the compiler keeps the original initialization order in a
-// translation unit and we need to respect that.
-// For more detail, read the section of the GCC's manual about init_priority.
-template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
-  // Sort sections by priority.
-  typedef std::pair<int, InputSection<ELFT> *> Pair;
+template <class ELFT>
+void OutputSection<ELFT>::sort(
+    std::function<unsigned(InputSection<ELFT> *S)> Order) {
+  typedef std::pair<unsigned, InputSection<ELFT> *> Pair;
   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
 
   std::vector<Pair> V;
   for (InputSection<ELFT> *S : Sections)
-    V.push_back({getPriority(S->Name), S});
+    V.push_back({Order(S), S});
   std::stable_sort(V.begin(), V.end(), Comp);
   Sections.clear();
   for (Pair &P : V)
     Sections.push_back(P.second);
 }
 
+// Sorts input sections by section name suffixes, so that .foo.N comes
+// before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
+// We want to keep the original order if the priorities are the same
+// because the compiler keeps the original initialization order in a
+// translation unit and we need to respect that.
+// For more detail, read the section of the GCC's manual about init_priority.
+template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
+  // Sort sections by priority.
+  sort([](InputSection<ELFT> *S) { return getPriority(S->Name); });
+}
+
 // Returns true if S matches /Filename.?\.o$/.
 static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
   if (!S.endswith(".o"))
     return false;
   S = S.drop_back(2);
   if (S.endswith(Filename))
     return true;
   return !S.empty() && S.drop_back().endswith(Filename);

lld/trunk/ELF/Relocations.cpp

for (const Elf_Sym &S : SS->file()->getGlobalSymbols()) {
     Alias->NeedsCopyOrPltAddr = true;
     Alias->symbol()->IsUsedInRegularObj = true;
   }
   Out<ELFT>::RelaDyn->addReloc(
       {Target->CopyRel, Out<ELFT>::Bss, SS->OffsetInBss, false, SS, 0});
 }
 
 template <class ELFT>
-static StringRef getSymbolName(const elf::ObjectFile<ELFT> &File,
-                               SymbolBody &Body) {
-  if (Body.isLocal() && Body.getNameOffset())
-    return File.getStringTable().data() + Body.getNameOffset();
-  if (!Body.isLocal())
-    return Body.getName();
-  return "";
-}
-
-template <class ELFT>
 static RelExpr adjustExpr(const elf::ObjectFile<ELFT> &File, SymbolBody &Body,
                           bool IsWrite, RelExpr Expr, uint32_t Type,
                           const uint8_t *Data) {
   bool Preemptible = isPreemptible(Body, Type);
   if (Body.isGnuIFunc()) {
     Expr = toPlt(Expr);
   } else if (!Preemptible) {
     if (needsPlt(Expr))
       Expr = fromPlt(Expr);
     if (Expr == R_GOT_PC && !isAbsoluteValue<ELFT>(Body))
       Expr = Target->adjustRelaxExpr(Type, Data, Expr);
   }
   Expr = Target->getThunkExpr(Expr, Type, File, Body);
 
   if (IsWrite || isStaticLinkTimeConstant<ELFT>(Expr, Type, Body))
     return Expr;
 
   // This relocation would require the dynamic linker to write a value to read
   // only memory. We can hack around it if we are producing an executable and
   // the refered symbol can be preemepted to refer to the executable.
   if (Config->Shared || (Config->Pic && !isRelExpr(Expr))) {
-    StringRef Name = getSymbolName(File, Body);
+    StringRef Name = getSymbolName(File.getStringTable(), Body);
     error("can't create dynamic relocation " + getRelName(Type) + " against " +
           (Name.empty() ? "readonly segment" : "symbol " + Name));
     return Expr;
   }
   if (Body.getVisibility() != STV_DEFAULT) {
     error("cannot preempt symbol " + Body.getName());
     return Expr;
   }
std::string getLocation(InputSectionBase<ELFT> &S, typename ELFT::uint Offset) {
   // missing, we use an actual filename.
   std::string SrcFile = File->SourceFile;
   if (SrcFile.empty())
     SrcFile = getFilename(File);
 
   // Find a symbol at a given location.
   DefinedRegular<ELFT> *Encl = getSymbolAt(&S, Offset);
   if (Encl && Encl->Type == STT_FUNC) {
-    StringRef Func = getSymbolName(*File, *Encl);
+    StringRef Func = getSymbolName(File->getStringTable(), *Encl);
     return SrcFile + " (function " + maybeDemangle(Func) + ")";
   }
 
   // If there's no symbol, print out the offset instead of a symbol name.
   return (SrcFile + " (" + S.Name + "+0x" + Twine::utohexstr(Offset) + ")")
       .str();
 }
 

lld/trunk/ELF/Symbols.h

 }
 
 inline Symbol *SymbolBody::symbol() {
   assert(!isLocal());
   return reinterpret_cast<Symbol *>(reinterpret_cast<char *>(this) -
                                     offsetof(Symbol, Body));
 }
 
+StringRef getSymbolName(StringRef SymTab, SymbolBody &Body);
+
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/Symbols.cpp

if (B->isUndefined())
     outs() << ": reference to ";
   else if (B->isCommon())
     outs() << ": common definition of ";
   else
     outs() << ": definition of ";
   outs() << B->getName() << "\n";
 }
 
+StringRef elf::getSymbolName(StringRef SymTab, SymbolBody &Body) {
+  if (Body.isLocal() && Body.getNameOffset())
+    return SymTab.data() + Body.getNameOffset();
+  if (!Body.isLocal())
+    return Body.getName();
+  return "";
+}
+
 template bool SymbolBody::hasThunk<ELF32LE>() const;
 template bool SymbolBody::hasThunk<ELF32BE>() const;
 template bool SymbolBody::hasThunk<ELF64LE>() const;
 template bool SymbolBody::hasThunk<ELF64BE>() const;
 
 template uint32_t SymbolBody::template getVA<ELF32LE>(uint32_t) const;
 template uint32_t SymbolBody::template getVA<ELF32BE>(uint32_t) const;
 template uint64_t SymbolBody::template getVA<ELF64LE>(uint64_t) const;

lld/trunk/ELF/Writer.cpp

 }
 
 // Sort input sections by the special rule for .ctors and .dtors.
 template <class ELFT> static void sortCtorsDtors(OutputSectionBase *S) {
   if (S)
     reinterpret_cast<OutputSection<ELFT> *>(S)->sortCtorsDtors();
 }
 
+// Sort input sections using the list provided by --symbol-ordering-file.
+template <class ELFT>
+static void sortBySymbolsOrder(ArrayRef<OutputSectionBase *> V) {
+  if (Config->SymbolOrderingFile.empty())
+    return;
+
+  // Build sections order map from symbols list.
+  DenseMap<InputSectionBase<ELFT> *, unsigned> SectionsOrder;
+  for (elf::ObjectFile<ELFT> *File : Symtab<ELFT>::X->getObjectFiles()) {
+    for (SymbolBody *Body : File->getSymbols()) {
+      auto *D = dyn_cast<DefinedRegular<ELFT>>(Body);
+      if (!D || !D->Section)
+        continue;
+      StringRef SymName = getSymbolName(File->getStringTable(), *Body);
+      auto It = Config->SymbolOrderingFile.find(CachedHashString(SymName));
+      if (It == Config->SymbolOrderingFile.end())
+        continue;
+
+      auto It2 = SectionsOrder.insert({D->Section, It->second});
+      if (!It2.second)
+        It2.first->second = std::min(It->second, It2.first->second);
+    }
+  }
+
+  for (OutputSectionBase *Base : V)
+    if (OutputSection<ELFT> *Sec = dyn_cast<OutputSection<ELFT>>(Base))
+      Sec->sort([&](InputSection<ELFT> *S) {
+        auto It = SectionsOrder.find(S);
+        return It == SectionsOrder.end() ? UINT32_MAX : It->second;
+      });
+}
+
 template <class ELFT>
 void Writer<ELFT>::forEachRelSec(
     std::function<void(InputSectionBase<ELFT> &, const typename ELFT::Shdr &)>
         Fn) {
   for (InputSectionBase<ELFT> *IS : Symtab<ELFT>::X->Sections) {
     if (!IS->Live)
       continue;
     // Scan all relocations. Each relocation goes through a series
if (IsNew)
     OutputSections.push_back(Sec);
   Sec->addSection(IS);
 }
 
 template <class ELFT> void Writer<ELFT>::createSections() {
   for (InputSectionBase<ELFT> *IS : Symtab<ELFT>::X->Sections)
     addInputSec(IS);
 
+  sortBySymbolsOrder<ELFT>(OutputSections);
   sortInitFini<ELFT>(findSection(".init_array"));
   sortInitFini<ELFT>(findSection(".fini_array"));
   sortCtorsDtors<ELFT>(findSection(".ctors"));
   sortCtorsDtors<ELFT>(findSection(".dtors"));
 
   for (OutputSectionBase *Sec : OutputSections)
     Sec->assignOffsets();
 }

lld/trunk/test/ELF/symbol-ordering-file.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t.out
+# RUN: llvm-objdump -s %t.out| FileCheck %s --check-prefix=BEFORE
+
+# BEFORE:      Contents of section .foo:
+# BEFORE-NEXT:  11000 11223344 5566
+
+# RUN: echo "_foo4  " > %t_order.txt
+# RUN: echo "  _foo3" >> %t_order.txt
+# RUN: echo "_foo5" >> %t_order.txt
+# RUN: echo "_foo2" >> %t_order.txt
+# RUN: echo " " >> %t_order.txt
+# RUN: echo "_foo4" >> %t_order.txt
+# RUN: echo "_bar1" >> %t_order.txt
+# RUN: echo "_foo1" >> %t_order.txt
+
+# RUN: ld.lld --symbol-ordering-file %t_order.txt %t.o -o %t2.out
+# RUN: llvm-objdump -s %t2.out| FileCheck %s --check-prefix=AFTER
+
+# AFTER:      Contents of section .foo:
+# AFTER-NEXT:  11000 44335566 2211
+
+.section .foo,"ax",@progbits,unique,1
+_foo1:
+ .byte 0x11
+
+.section .foo,"ax",@progbits,unique,2
+_foo2:
+ .byte 0x22
+
+.section .foo,"ax",@progbits,unique,3
+_foo3:
+ .byte 0x33
+
+.section .foo,"ax",@progbits,unique,4
+_foo4:
+ .byte 0x44
+
+.section .foo,"ax",@progbits,unique,5
+_foo5:
+ .byte 0x55
+_bar1:
+ .byte 0x66