[ELF] Create output sections in LinkerScript class

[evgeny777]

Summary

Creating this patch according to George suggestion here
https://reviews.llvm.org/D19976

This patch moves output section creation from Writer<ELFT> to LinkerScript<ELFT>.
Input section order in linker script is respected and can be different from section order in input files.
All lld unit tests pass successfully without modification

The main goal of this patch is to give a go to https://reviews.llvm.org/D22215
and many other unsupported features (like symbol assignment, PROVIDE, PROVIDE_HIDDEN, e.t.c)

[grimar]

Though that patch is different from what I posted, I have no arguments for not to land it for now, until
possible redesign is under discussions. I have just cosmetic сomments about.

ELF/LinkerScript.cpp

199

This method seems to be a almost copy of elf::isDiscarded(). Do you really need it then ?

227

I would move Result below typedef, we usually declare typedefs at first lines of method.
Also it's naming is probably incorrect, I believe we do not use 2 uppercases character in a row for naming things. And I think do not leave a type in name (Up == Unique Ptr right ?)

232

We place dots at the end of comments.

237

I would write as

if (!isDiscarded(S))
  if (globMatch(R.SectionPattern, S->getSectionName())))

241

Ditto about dot.

243

Lets be consistent with code above:

InputSectionBase<ELFT> *S

ELF/LinkerScript.h

26

I think it is not in common in lld code to declare new type in globals.

36

Not relative change.

ELF/Writer.cpp

92

Looks you can leave Factory to be local object, it does not really needs to be member.
You can just give it to createSections/finalizeSections. I have no real preference here though.

[evgeny777]

ELF/LinkerScript.cpp

199

elf::isDiscarded no longer calls LinkerScript::isDiscarded and does not check S->OutSec.

ELF/Writer.cpp

92

It holds name-value section map. See OutputSectionFactory::create()

[grimar]

ELF/LinkerScript.cpp

199

I know, but you probably can check that separatelly and keep the common logic.

[ruiu]

ELF/LinkerScript.cpp

198

Having two functions with the same name (elf::isDicarded and LinkerScript::isDiscarded) is confusing because from LinkerScript class, the latter hides the former.

Can you move elf::isDiscarded to Writer.cpp and make it a static non-member function? Then the other isDiscarded is not visible from this file, so it is less confusing.

211

This is a helper function for createSections and heavily relies on it. I usually write such function as a lambda for readability -- such as Add in OutputSections.cpp.

228

For consistency, please remove this typedef.

245

Does this work? It adds the same section again if it is mentioned in a linker script.

ELF/LinkerScript.h

26

Yup. We don't usually do this, so it is better to avoid it for consistency.

ELF/Writer.cpp

613

Can you make this function return a vector of sections rather than mutating OwningSections? Then, I think you can remove OwningSections member from this class by making it a local variable in run.

[evgeny777]

ELF/LinkerScript.cpp

245

Yes. When input section is added to output section, the OutSec member variable of InputSectionBase<ELFT> class points to output section class instance. It is being checked inside LinkerScript<ELFT>::isDiscarded method:

return !S || !S->Live || S->OutSec || getOutputSection(S) == "/DISCARD/";

So input section can't be added twice

[evgeny777]

Review updated

[ruiu]

LGTM with the following changes.

ELF/LinkerScript.cpp

229

Do you need elf:: specifier? If not, please remove.

238

elf::

242

Add a space after if.

244–245

} else { (or, in general, please run clang-format-diff.)

ELF/Writer.cpp

239

OwningSections was named such because Writer owned sections using this variable. It is no longer the case. So please rename something different, say just Sections.

243–246

Why don't you use a regular for-each loop?

for (std::unique_ptr<OutputSectionBase<ELFT>> &S : OwningSections)
  OutputSections.push_back(S.get());

ELF/InputSection.cpp

 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
 template <class ELFT> bool elf::isDiscarded(InputSectionBase<ELFT> *S) {
-  return !S || S == &InputSection<ELFT>::Discarded || !S->Live ||
-         Script<ELFT>::X->isDiscarded(S);
+  return !S || S == &InputSection<ELFT>::Discarded || !S->Live;
 }
 
 template <class ELFT>
 InputSectionBase<ELFT>::InputSectionBase(elf::ObjectFile<ELFT> *File,
                                          const Elf_Shdr *Header,
                                          Kind SectionKind)
     : Header(Header), File(File), SectionKind(SectionKind), Repl(this),
       Compressed(Header->sh_flags & SHF_COMPRESSED) {

ELF/LinkerScript.h

 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 namespace lld {
 namespace elf {
+template <class ELFT> class InputSectionBase;
+template <class ELFT> class OutputSectionBase;
+template <class ELFT> class OutputSectionFactory;
+
+template<class ELFT>
+using OutputSectionList = std::vector<std::unique_ptr<OutputSectionBase<ELFT>>>;
 
 // Parses a linker script. Calling this function updates
 // Config and ScriptConfig.
 void readLinkerScript(MemoryBufferRef MB);
 
 class ScriptParser;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class OutputSectionBase;
 
 // This class represents each rule in SECTIONS command.
 struct SectionRule {
   SectionRule(StringRef D, StringRef S)
       : Dest(D), SectionPattern(S) {}
 
   StringRef Dest;
-
   StringRef SectionPattern;
 };
 
 // This enum represents what we can observe in SECTIONS tag of script:
 // ExprKind is a location counter change, like ". = . + 0x1000"
 // SectionKind is a description of output section, like ".data :..."
 enum SectionsCommandKind { SectionKind, AssignmentKind };
 

 template <class ELFT> class LinkerScript {
   typedef typename ELFT::uint uintX_t;
 
 public:
   StringRef getOutputSection(InputSectionBase<ELFT> *S);
   ArrayRef<uint8_t> getFiller(StringRef Name);
   bool isDiscarded(InputSectionBase<ELFT> *S);
   bool shouldKeep(InputSectionBase<ELFT> *S);
+  OutputSectionList<ELFT> createSections(OutputSectionFactory<ELFT> &Factory);
   void assignAddresses(ArrayRef<OutputSectionBase<ELFT> *> S);
   int compareSections(StringRef A, StringRef B);
   void addScriptedSymbols();
 
 private:
   // "ScriptConfig" is a bit too long, so define a short name for it.
   ScriptConfiguration &Opt = *ScriptConfig;
 

ELF/LinkerScript.cpp

 #include "Driver.h"
 #include "InputSection.h"
 #include "OutputSections.h"
 #include "ScriptParser.h"
 #include "Strings.h"
 #include "Symbols.h"
 #include "SymbolTable.h"
 #include "Target.h"
+#include "Writer.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/ELF.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace llvm;

 StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
   for (SectionRule &R : Opt.Sections)
     if (globMatch(R.SectionPattern, S->getSectionName()))
       return R.Dest;
   return "";
 }
 
 template <class ELFT>
 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
-  return getOutputSection(S) == "/DISCARD/";
+  return !S || !S->Live || S->OutSec || getOutputSection(S) == "/DISCARD/";
 }
 
 template <class ELFT>
 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
   for (StringRef Pat : Opt.KeptSections)
     if (globMatch(Pat, S->getSectionName()))
       return true;
   return false;
 }
 
 template <class ELFT>
+static void addInputSection(
+    OutputSectionFactory<ELFT> &Factory, InputSectionBase<ELFT> *C,
+    StringRef OutSecName,
+    std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> &OutSecList) {
+
+  OutputSectionBase<ELFT> *Sec;
+  bool IsNew;
+  std::tie(Sec, IsNew) = Factory.create(C, OutSecName);
+  if (IsNew)
+    OutSecList.emplace_back(Sec);
+  Sec->addSection(C);
+}
+
+template <class ELFT>
+OutputSectionList<ELFT>
+LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
+  OutputSectionList<ELFT> Result;
+  typedef std::unique_ptr<elf::ObjectFile<ELFT>> ObjectFileUP;
+
+  // Select input sections matching rule and add them to corresponding
+  // output section. Section rules are processed in order they're listed
+  // in script, so correct input section order is maintained by design
+  for (SectionRule &R : Opt.Sections)
+    for (const ObjectFileUP &F : Symtab<ELFT>::X->getObjectFiles())
+      for (InputSectionBase<ELFT> *S : F->getSections())
+        if (!isDiscarded(S) &&
+            globMatch(R.SectionPattern, S->getSectionName()))
+          // Add single input section to output section
+          addInputSection(Factory, S, R.Dest, Result);
+
+  // Add all other input sections, which are not listed in script
+  for (const ObjectFileUP &F : Symtab<ELFT>::X->getObjectFiles())
+    for (InputSectionBase<ELFT> *C : F->getSections())
+      if (!isDiscarded(C))
+        addInputSection(Factory, C, getOutputSectionName(C), Result);
+
+  return Result;
+}
+
+template <class ELFT>
 void LinkerScript<ELFT>::assignAddresses(
     ArrayRef<OutputSectionBase<ELFT> *> Sections) {
   // 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 : Sections) {

ELF/Writer.cpp

struct Phdr {
     Elf_Phdr H = {};
     OutputSectionBase<ELFT> *First = nullptr;
     OutputSectionBase<ELFT> *Last = nullptr;
   };
 
   void copyLocalSymbols();
   void addReservedSymbols();
   void createSections();
+  void finalizeSections();
   void addPredefinedSections();
   bool needsGot();
 
   void createPhdrs();
   void assignAddresses();
   void assignFileOffsets();
   void setPhdrs();
   void fixHeaders();
private:
   }
 
   void addCommonSymbols(std::vector<DefinedCommon *> &Syms);
 
   std::unique_ptr<FileOutputBuffer> Buffer;
 
   BumpPtrAllocator Alloc;
   std::vector<OutputSectionBase<ELFT> *> OutputSections;
-  std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> OwningSections;
+  OutputSectionList<ELFT> OwningSections;
+  OutputSectionFactory<ELFT> Factory;
 
   void addRelIpltSymbols();
   void addStartEndSymbols();
   void addStartStopSymbols(OutputSectionBase<ELFT> *Sec);
 
   SymbolTable<ELFT> &Symtab;
   std::vector<Phdr> Phdrs;
 
template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
   Writer<ELFT>(*Symtab).run();
 }
 
 // The main function of the writer.
 template <class ELFT> void Writer<ELFT>::run() {
   if (!Config->DiscardAll)
     copyLocalSymbols();
   addReservedSymbols();
+  
+  if (ScriptConfig->DoLayout)
+    OwningSections = Script<ELFT>::X->createSections(Factory);
+  else
     createSections();
+  finalizeSections();
   if (HasError)
     return;
 
   if (Config->Relocatable) {
     assignFileOffsets();
   } else {
     createPhdrs();
     fixHeaders();
     if (ScriptConfig->DoLayout) {
       Script<ELFT>::X->assignAddresses(OutputSections);
     } else {

 }
 
 // Sort input sections by the special rule for .ctors and .dtors.
 template <class ELFT> static void sortCtorsDtors(OutputSectionBase<ELFT> *S) {
   if (S)
     reinterpret_cast<OutputSection<ELFT> *>(S)->sortCtorsDtors();
 }
 
-// Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::createSections() {
-  // Create output sections for input object file sections.
-  std::vector<OutputSectionBase<ELFT> *> RegularSections;
-  OutputSectionFactory<ELFT> Factory;
   for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
        Symtab.getObjectFiles()) {
     for (InputSectionBase<ELFT> *C : F->getSections()) {
       if (isDiscarded(C)) {
         reportDiscarded(C, F);
         continue;
       }
       OutputSectionBase<ELFT> *Sec;
       bool IsNew;
       std::tie(Sec, IsNew) = Factory.create(C, getOutputSectionName(C));
-      if (IsNew) {
+      if (IsNew)
         OwningSections.emplace_back(Sec);
-        OutputSections.push_back(Sec);
-        RegularSections.push_back(Sec);
-      }
+
       Sec->addSection(C);
     }
   }
+}
+
+// Create output section objects and add them to OutputSections.
+template <class ELFT> void Writer<ELFT>::finalizeSections() {
+  // Create output sections for input object file sections.
+  std::vector<OutputSectionBase<ELFT> *> RegularSections;
+
+  for (std::unique_ptr<OutputSectionBase<ELFT>> &OutSec : OwningSections) {
+    OutputSections.push_back(OutSec.get());
+    RegularSections.push_back(OutSec.get());
+  }
 
   // If we have a .opd section (used under PPC64 for function descriptors),
   // store a pointer to it here so that we can use it later when processing
   // relocations.
   Out<ELFT>::Opd = Factory.lookup(".opd", SHT_PROGBITS, SHF_WRITE | SHF_ALLOC);
 
   Out<ELFT>::Dynamic->PreInitArraySec = Factory.lookup(
       ".preinit_array", SHT_PREINIT_ARRAY, SHF_WRITE | SHF_ALLOC);