[ELF] - Get rid of SectionOrder array.

[grimar]

Summary

SectionOrder vector was a part of LinkerScript class.

After commit of D18499 it can be removed because Locations vector
contains the same information and SectiorOrder is just a subset.

[grimar]

ELF/LinkerScript.cpp

172

So compareSections() is used to sort OutputSections.
Later linkerscript uses this order in fixupLocations() to add orphans.

Therefore Locations vector is updated at the very end,
before actual address assignment.

Another variant would be to call fixupLocations() earlier, before compareSections().
Then orpan order would be script driven, but will add some code complexity as will need export of
fixupLocations() method.

I like both approach. First (this patch) for simple code, second for giving
all cards to script to control orphans order.

[grimar]

This patch also fixes the section indexes. We should keep OutputSections order the same as Locations order because of code that assigns them:

unsigned I = 1;
for (OutputSectionBase<ELFT> *Sec : OutputSections) {
  Sec->SectionIndex = I++;
  Sec->setSHName(Out<ELFT>::ShStrTab->addString(Sec->getName()));
}

[• rafael]

I think this is fine, but I will let Rui have the final say on liker script stuff.

[ruiu]

LGTM with a nit.

ELF/LinkerScript.cpp

93

The return value will never overflow in reality, so let's use just int instead of uint32_t. Then you can report the absent key as just -1 instead of UINT32_MAX.

[grimar]

ELF/LinkerScript.cpp

93

Doing that will require changes that might overcomplicate the current
code of compareSections():

uint32_t I = getSectionOrder(A);
uint32_t J = getSectionOrder(B);
if (I == (uint32_t)-1 && J == (uint32_t)-1)
  return 0;
return I < J ? -1 : 1;

For example if I has some order, but J does not then:
Since J is uint32_t (and == UINT32_MAX) then I < J will work as expected, placing A before B.

If we switch to int then I guess something like next should be written
(and it does not seem to worth that):

int I = getSectionOrder(A);
int J = getSectionOrder(B);
if (I == -1 && J == -1)
  return 0;
if (I == -1)
  return 1;
if (J == -1)
  return -1;
return I < J ? -1 : 1;

So I committed without that change for now.

[ruiu]

ELF/LinkerScript.cpp

172

Makes sense, but in that case (uint32_t)-1 is not an error code, but it actually mean the sorting order of the given section name (e.g. the lowest priority). In that case (uint32_t)-1 looks odd. Please use UINT32_MAX instead because it's what you really mean. Also it needs a comment about when UINT32_MAX returns.

Also, there's no reason to use uint32_t. I'd use int and INT_MAX.

ELF/LinkerScript.h

public:
 
   bool Exists = false;
 
 private:
   template <class ELFT>
   void fixupLocations(std::vector<OutputSectionBase<ELFT> *> &);
   uint64_t evaluate(std::vector<StringRef> &Tokens, uint64_t LocCounter);
   template <class ELFT> SectionRule *find(InputSectionBase<ELFT> *S);
+  uint32_t getSectionOrder(StringRef Name);
 
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
-  // Output sections are sorted by this order.
-  std::vector<StringRef> SectionOrder;
-
   // Section fill attribute for each section.
   llvm::StringMap<std::vector<uint8_t>> Filler;
 
   // Used to assign addresses to sections.
   std::vector<LocationNode> Locations;
 
   llvm::BumpPtrAllocator Alloc;
 };
 
 extern LinkerScript *Script;
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/LinkerScript.cpp

bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
   return getOutputSection(S) == "/DISCARD/";
 }
 
 template <class ELFT> bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
   SectionRule *R = find(S);
   return R && R->Keep;
 }
 
+uint32_t LinkerScript::getSectionOrder(StringRef Name) {
+  auto Begin = Locations.begin();
+  auto End = Locations.end();
+  auto I = std::find_if(Begin, End, [&](LocationNode &N) {
+    return N.Type == Command::Section && N.SectionName == Name;
+  });
+  return I == End ? (uint32_t)-1 : (I - Begin);
+}
+
 // This method finalizes the Locations list. Adds neccesary locations for
 // orphan sections, what prepares it for futher use without
 // changes in LinkerScript::assignAddresses().
 template <class ELFT>
 void LinkerScript::fixupLocations(std::vector<OutputSectionBase<ELFT> *> &S) {
   // Orphan sections are sections present in the input files which
   // are not explicitly placed into the output file by the linker
   // script. We place orphan sections at end of file. Other linkers places
   // them using some heuristics as described in
   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
   for (OutputSectionBase<ELFT> *Sec : S) {
     StringRef Name = Sec->getName();
-    auto I = std::find(SectionOrder.begin(), SectionOrder.end(), Name);
-    if (I == SectionOrder.end())
+    if (getSectionOrder(Name) == (uint32_t)-1)
       Locations.push_back({Command::Section, {}, {Name}});
   }
 }
 
 template <class ELFT>
 void LinkerScript::assignAddresses(std::vector<OutputSectionBase<ELFT> *> &S) {
   typedef typename ELFT::uint uintX_t;
 

 
 ArrayRef<uint8_t> LinkerScript::getFiller(StringRef Name) {
   auto I = Filler.find(Name);
   if (I == Filler.end())
     return {};
   return I->second;
 }
 
-// A compartor to sort output sections. Returns -1 or 1 if both
-// A and B are mentioned in linker scripts. Otherwise, returns 0
+// A compartor to sort output sections. Returns -1 or 1 if
+// A or B are mentioned in linker script. Otherwise, returns 0
 // to use the default rule which is implemented in Writer.cpp.
 int LinkerScript::compareSections(StringRef A, StringRef B) {
-  auto E = SectionOrder.end();
-  auto I = std::find(SectionOrder.begin(), E, A);
-  auto J = std::find(SectionOrder.begin(), E, B);
-  if (I == E || J == E)
+  uint32_t I = getSectionOrder(A);
+  uint32_t J = getSectionOrder(B);
+  if (I == (uint32_t)-1 && J == (uint32_t)-1)
     return 0;
   return I < J ? -1 : 1;
 }
 
 // Returns true if S matches T. S can contain glob meta-characters.
 // The asterisk ('*') matches zero or more characacters, and the question
 // mark ('?') matches one character.
 static bool matchStr(StringRef S, StringRef T) {
while (!Error) {
     Node.Expr.push_back(Tok);
   }
   if (Node.Expr.empty())
     error("error in location counter expression");
 }
 
 void ScriptParser::readOutputSectionDescription() {
   StringRef OutSec = next();
-  Script->SectionOrder.push_back(OutSec);
   Script->Locations.push_back({Command::Section, {}, {OutSec}});
   expect(":");
   expect("{");
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
       readSectionPatterns(OutSec, false);
     } else if (Tok == "KEEP") {

test/ELF/linkerscript-orphans.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: echo "SECTIONS { .writable : { *(.writable) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -section-headers %t.out | \
+# RUN:   FileCheck -check-prefix=TEXTORPHAN %s
+
+# RUN: echo "SECTIONS { .text : { *(.text) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -section-headers %t.out | \
+# RUN:   FileCheck -check-prefix=WRITABLEORPHAN %s
+
+# TEXTORPHAN:      Sections:
+# TEXTORPHAN-NEXT: Idx Name
+# TEXTORPHAN-NEXT:   0
+# TEXTORPHAN-NEXT:   1 .writable
+# TEXTORPHAN-NEXT:   2 .text
+
+# WRITABLEORPHAN:      Sections:
+# WRITABLEORPHAN-NEXT: Idx Name
+# WRITABLEORPHAN-NEXT:   0
+# WRITABLEORPHAN-NEXT:   1 .text
+# WRITABLEORPHAN-NEXT:   2 .writable
+
+.global _start
+_start:
+ nop
+
+.section .writable,"aw"
+ .zero 4