[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

27

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

37

Not relative change.

ELF/Writer.cpp

75

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

75

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

27

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

ELF/Writer.cpp

640–645

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

222

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.

226–229

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.h

 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf {
 
-template <class ELFT> bool isDiscarded(InputSectionBase<ELFT> *S);
-
 class SymbolBody;
 
 template <class ELFT> class ICF;
 template <class ELFT> class DefinedRegular;
 template <class ELFT> class ObjectFile;
 template <class ELFT> class OutputSection;
 template <class ELFT> class OutputSectionBase;
 

ELF/InputSection.cpp

 using namespace llvm;
 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);
-}
-
 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) {
   // The garbage collector sets sections' Live bits.
   // If GC is disabled, all sections are considered live by default.
MipsOptionsInputSection<ELFT>::MipsOptionsInputSection(elf::ObjectFile<ELFT> *F,
   }
 }
 
 template <class ELFT>
 bool MipsOptionsInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
   return S->SectionKind == InputSectionBase<ELFT>::MipsOptions;
 }
 
-template bool elf::isDiscarded<ELF32LE>(InputSectionBase<ELF32LE> *);
-template bool elf::isDiscarded<ELF32BE>(InputSectionBase<ELF32BE> *);
-template bool elf::isDiscarded<ELF64LE>(InputSectionBase<ELF64LE> *);
-template bool elf::isDiscarded<ELF64BE>(InputSectionBase<ELF64BE> *);
-
 template class elf::InputSectionBase<ELF32LE>;
 template class elf::InputSectionBase<ELF32BE>;
 template class elf::InputSectionBase<ELF64LE>;
 template class elf::InputSectionBase<ELF64BE>;
 
 template class elf::InputSection<ELF32LE>;
 template class elf::InputSection<ELF32BE>;
 template class elf::InputSection<ELF64LE>;

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;
 
 // 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 };
 

 
 public:
   typedef PhdrEntry<ELFT> Phdr;
 
   StringRef getOutputSection(InputSectionBase<ELFT> *S);
   ArrayRef<uint8_t> getFiller(StringRef Name);
   bool isDiscarded(InputSectionBase<ELFT> *S);
   bool shouldKeep(InputSectionBase<ELFT> *S);
+  std::vector<std::unique_ptr<OutputSectionBase<ELFT>>>
+  createSections(OutputSectionFactory<ELFT> &Factory);
   void assignAddresses(ArrayRef<OutputSectionBase<ELFT> *> S);
   int compareSections(StringRef A, StringRef B);
   void addScriptedSymbols();
   std::vector<Phdr> createPhdrs(ArrayRef<OutputSectionBase<ELFT> *> S);
   bool hasPhdrsCommands();
 
 private:
   // "ScriptConfig" is a bit too long, so define a short name for it.

ELF/LinkerScript.cpp

 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 || 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>
+std::vector<std::unique_ptr<OutputSectionBase<ELFT>>>
+LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
+  std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> Result;
+  // Add input section to output section. If there is no output section yet,
+  // then create it and add to output section list.
+  auto AddInputSec = [&](InputSectionBase<ELFT> *C, StringRef Name) {
+    OutputSectionBase<ELFT> *Sec;
+    bool IsNew;
+    std::tie(Sec, IsNew) = Factory.create(C, Name);
+    if (IsNew)
+      Result.emplace_back(Sec);
+    Sec->addSection(C);
+  };
+
+  // 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 std::unique_ptr<elf::ObjectFile<ELFT>> &F :
+         Symtab<ELFT>::X->getObjectFiles())
+      for (InputSectionBase<ELFT> *S : F->getSections())
+        if (!isDiscarded(S) && !S->OutSec &&
+            globMatch(R.SectionPattern, S->getSectionName()))
+          // Add single input section to output section.
+          AddInputSec(S, R.Dest);
+
+  // Add all other input sections, which are not listed in script.
+  for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
+       Symtab<ELFT>::X->getObjectFiles())
+    for (InputSectionBase<ELFT> *S : F->getSections())
+      if (!isDiscarded(S)) {
+        if(!S->OutSec)
+          AddInputSec(S, getOutputSectionName(S));
+      }
+      else
+        reportDiscarded(S, F);
+
+  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

public:
   Writer(SymbolTable<ELFT> &S) : Symtab(S) {}
   void run();
 
 private:
   typedef PhdrEntry<ELFT> Phdr;
 
   void copyLocalSymbols();
   void addReservedSymbols();
-  void createSections();
+  std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> createSections();
+  void finalizeSections();
   void addPredefinedSections();
   bool needsGot();
 
   void createPhdrs();
   void assignAddresses();
   void assignFileOffsets();
   void setPhdrs();
   void fixHeaders();
   void fixSectionAlignments();
   void fixAbsoluteSymbols();
   void openFile();
   void writeHeader();
   void writeSections();
   void writeBuildId();
 
   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;
+  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();
-  createSections();
+
+  std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> OwningSections =
+      ScriptConfig->DoLayout ? Script<ELFT>::X->createSections(Factory)
+                             : createSections();
+
+  std::for_each(OwningSections.begin(), OwningSections.end(),
+                [&](std::unique_ptr<OutputSectionBase<ELFT>> &Sec) {
+                  OutputSections.push_back(Sec.get());
+                });
+  finalizeSections();
   if (HasError)
     return;
 
   if (Config->Relocatable) {
     assignFileOffsets();
   } else {
     if (Script<ELFT>::X->hasPhdrsCommands())
       Phdrs = Script<ELFT>::X->createPhdrs(OutputSections);
template <class ELFT> bool elf::needsInterpSection() {
   return !Symtab<ELFT>::X->getSharedFiles().empty() &&
          !Config->DynamicLinker.empty();
 }
 
 template <class ELFT> bool elf::isOutputDynamic() {
   return !Symtab<ELFT>::X->getSharedFiles().empty() || Config->Pic;
 }
 
+template <class ELFT> static bool isDiscarded(InputSectionBase<ELFT> *S) {
+  return !S || S == &InputSection<ELFT>::Discarded || !S->Live;
+}
+
 // Program header entry
 template<class ELFT>
 PhdrEntry<ELFT>::PhdrEntry(unsigned Type, unsigned Flags) {
   H.p_type = Type;
   H.p_flags = Flags;
 }
 
 template<class ELFT>
if (S)
     reinterpret_cast<OutputSection<ELFT> *>(S)->sortInitFini();
 }
 
 // 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;
+template <class ELFT>
+std::vector<std::unique_ptr<OutputSectionBase<ELFT>>>
+Writer<ELFT>::createSections() {
+  std::vector<std::unique_ptr<OutputSectionBase<ELFT>>> Result;
+
   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) {
-        OwningSections.emplace_back(Sec);
-        OutputSections.push_back(Sec);
-        RegularSections.push_back(Sec);
-      }
+      if (IsNew)
+        Result.emplace_back(Sec);
+
       Sec->addSection(C);
     }
   }
+  return Result;
+}
+
+// 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 = OutputSections;
 
   // 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);