[ELF] - Prototype of possible linkerscript redesign.

[grimar]

Summary

Patch implements command driven linker script logic.
ScriptConfiguration class contains only a list of commands after
applying. No more any other temporarily representation.

That should allow to implement any scriopt feature I believe since
at any point it is possible to iterate over commands list and
process them accordinly.

Also one of the point is the creation of sections at linker side
and separating logic of script from any other part of linker
as much as possible.

[ruiu]

Before going into details, can I ask you if you think this is going to be able to support all the linker script features? Is there any concerns/limitations on it?

[grimar]

In D19976#423173, @ruiu wrote:

Before going into details, can I ask you if you think this is going to be able to support all the linker script features? Is there any concerns/limitations on it?

I think this approach should be pretty efficient.
I reviewed again freebsd script and I think all commands it uses can be implemented with this approach without
hacks or anything alike. I can not imagine a real limitations. The way it works seems very natural to me,
because of 2 main steps that are separated and do not cross at all.

1. Creating sections and processing all commands inside declaration to finally get

a output section as a black box for future use. This allows to make any internal layout and
support every internal command (it seems). The fact that location counter
meaning inside declaration differs from meaning outside very helpfull here and strengthens my faith.
For example PROVIDE inside declarations is easy to support because we know (.) value that is offset here,
we can move it, align or whatever we want, we can place sections in the order we want, sort them, keep or discard,
that all is also easy because on each step we have direct access to linkerscipt commands and have no any other
task except "create output section".

2. Assign addresses and processing external to sections declarations commands is very comfortable to do now.

For example PROVIDE on that step requires global (.) value and that is what easily we can give it.
We do not need to bother here with internals of sections, because external commands can not affect them and
we already have sections created at step 1, so we skip all that stuff during processing.
We don't need to sort them here, as it is assumed they are already sorted after step 1.
And again we have direct access to linkerscript sections commands on this step as well
(actually current code gives ability to read/interpret them at any point of program), so we definetely should
be able to implement everything we might want, since there is no any information lost.

Now about my conserns.
The only I have is about processing predefined sections.
Now in this patch they are not processed, so they are just added to the end of outputsections list
in addPredefinedSections(). I think since script is responsible for full layout now, them should be processed
on its side either. So I mean if we see (for example):

.got            : { *(.got) }
.got.plt        : { *(.got.plt) }

Then we want to place Out<ELFT>::Got and Out<ELFT>::GotPlt in that order in some generalized way.
We can probably just add all predefined sections to the end
and then sort the list at the end of step 1, since we know their names and we have matching pattern.
Or we can assume that ".got" is always Out<ELFT>::Got and so on, or process them in some nicer way.
So that is definetely possible, just requires some attention for clean implementation.
I would leave that for futher patches.

[grimar]

ping ?

[grimar]

Ping ?

[grimar]

Ping ?

[davide]

Rui, can you please take a look when you get a chance? Thanks!

[davide]

Thanks for taking care of this, George.
The first question that comes to my mind is: how is this code going to support expression relative to sections? When we do symbol assignment a symbol may be relative to a section so we need to be able to fetch the section (which was a little bit of a stretch in the current code).

My second question is:
Can you defend the ability of your code being able to implement cleanly more complex constructs? e.g.

KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .dtors))
KEEP (*(SORT(.dtors.*)))

[grimar]

In D19976#473736, @davide wrote:

Thanks for taking care of this, George.
The first question that comes to my mind is: how is this code going to support expression relative to sections? When we do symbol assignment a symbol may be relative to a section so we need to be able to fetch the section (which was a little bit of a stretch in the current code).

Core idea of the patch turns around LayoutParser class that has run(Callback C) method. It can be used in any place of code,
providing the ability to retrive and proccess linker script section's tag commands that are actual for the place of call.
So speaking about expressions relative to sections: patch has LinkerScript<ELFT>::createSections() method that
main intend is to create all sections and process all commands that are inside output section declararions (including expressions and everything else).
Since location pointer inside output section declaration is relative to section and we have access to all linkerscript commands at that point,
we should be able to process them and perform any layout and expression calculations we want. Just because we have everything for that at this point.

My second question is:
Can you defend the ability of your code being able to implement cleanly more complex constructs? e.g.

KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .dtors))
KEEP (*(SORT(.dtors.*)))

We should be able to do that because will have access to all sections tag commands of script at any point and will be able to process them using custom callback we put to LayoutParser::run(Callback C). We might need to extend enum CommandKind with more types of commands and update the callback(s) properly.
What nice here that linkerscript code will be updated only in part of adding new commands to CommandKind.
And callback(s) can handle everything else.
Speaking about how clean it can be: everything will depend on callback implementation here. I believe it should be possible to implement nice and clean ones.

[ruiu]

I'll take a look at this tomorrow.

[davide]

In D19976#477596, @ruiu wrote:

I'll take a look at this tomorrow.

Thanks Rui.

[ruiu]

This is a fairly large patch -- you moved code between files and add new features. I'd appreciate if you do this incrementally in future.

ELF/LinkerScript.cpp

283

This seems tricky. Why do you have to parse linker scripts while processing expressions? I don't see a reason to use a callback function here. It seems to me that we can instead parse all scripts to save commands to a vector and evaluate them in this function.

ELF/MarkLive.cpp

185 ↗

(On Diff #56288)

What's wrong with this code? Why did you have to change the way we handle KEEP commands? The new code seems more complicated than before.

ELF/OutputSections.h

686

Move the definition to the .cpp file.

727–740

Can you move them to the .cpp?

ELF/Writer.cpp

109

This function is called only when a given section is discarded, so checking !IS || IS->Live seems redundant.

111

Remove llvm::.

625–626

Can you move this to createSections?

629–630

Now the function gets much smaller, we don't give a long name to this variable.

634

*F.get() -> *F

655

for (OutputSectionBase<ELFT> *Sec : createRegularSections()) {

818–822

Move this after BuildId so that you can write

if (needsInterpSection())
  OutputSections.insert(OutputSections.begin(), Out<ELFT>::Interp);

ELF/Writer.h

31 ↗

(On Diff #56288)

This function should belong to InputSections.h instead of this header.

[grimar]

In D19976#479048, @ruiu wrote:

This is a fairly large patch -- you moved code between files and add new features. I'd appreciate if you do this incrementally in future.

I think that was what I did initially.
D19977, D19981, D20104 patches were posted earlier to remove noise from this one.
I pointed that in comments for them, also this one depends on first 2 at least,
so if we land them I`ll be able to rebase this patch and reduce the amount of changes.

[grimar]

Rui, thanks for review.
I noticed that most of comments are relative to code movements that I was need to do for this patch.
So some times it is even not my changes at all.
That changes belongs to 3 patches mentioned above: D19977, D19981, D20104.
May be it would be reasonable for me to rebase these 3 and land them at first to remove noise from this patch ?

[grimar]

So I am trying to rebase this now, I hope to finish and update it tomorrow.

[davide]

Yes, please rebase so we can review more easily.

[grimar]

In D19976#483122, @davide wrote:

Yes, please rebase so we can review more easily.

Need a bit more time unfortunately, I`ll update tomorrow I guess.

[grimar]

• Rebased/updated the patch, addressed review comments.

[grimar]

So I rebased this. Currently there are 11 testcases failing, that what also was before the rebase and I am working on fix for that. But the patch still shows the concept I am suggesting.

ELF/LinkerScript.cpp

283

Agree. That was overcomplication.

ELF/MarkLive.cpp

185 ↗

(On Diff #56288)

I reverted that place and implemented shouldKeep() to keep the previous interface.

[evgeny777]

Though, I'm quite new to lld development, I think this code can be simplified. Here is my version of createSections()
It simply iterates over SectionRule array, selects input sections matching each rule, and adds them output section

template <class ELFT>
OutputSectionList LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
   OutputSectionList 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 (!elf::isDiscarded(S) && globMatch(R.SectionPattern, S->getSectionName())) 
             // Adds input section to output section collection
             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 (C->OutSec == nullptr)
        addInputSection(Factory, C, getOutputSectionName(C), Result);
    }
  }
  return Result;
}

Then in Writer<ELFT> I'm dispatching to correct version of createSections(), just like you're doing.

It's several times shorter and passes all unit tests.
I might be missing some important strategic move, which is introduced by your patch, so let's wait and see what others will say.

ELF/LinkerScript.cpp

205–218

I wonder, if we can live without script parser refactoring for the very first iteration.
May be this can be done as a separate review?

279

I wonder why do you now mix SectionsRule (which is now InputSectionKind) and SectionsCommand (now OutputSectionKind) into one Command object? Every time you iterate Opt.LayoutParser->Commands, you need either rules or commands, never both. May be it makes sense to have two separate collections, like we had before?

318

You seem to ignore comment in original version of assignAddresses:

// Find all the sections with required name. There can be more than
// ont section with such name, if the alignment, flags or type
// attribute differs.

448

Do we need to insert to Assigned here? Looks like, we're doing the final processing step

465

See my previous comment about mixing section rules and commands.

[grimar]

In D19976#485415, @evgeny777 wrote:

Though, I'm quite new to lld development, I think this code can be simplified. Here is my version of createSections()

Can you post a patch then ? I think it is fine to have few visions and chose the most appropriate. Though my one removes a lot of things, so I belive it is useful change.

ELF/LinkerScript.cpp

205–218

Not sure here as this patch itself in my understanding a kind of refactoring.

279

I am not sure what is better. Just afraid that to have 2 collections is a overcomplication itself. Though I`ll think about that.

318

Yes, thanks, this patch uses a bit outdated code. I am going to update it when fix the testcases, though still interested to see general comments.

448

Yes, I think I can remove that, thanks.

[majnemer]

ELF/LinkerScript.cpp

49

Why not just use an ArrayRef<StringRef>?

81

Ditto.

282

Consider using llvm::find_if, it's a little more concise.

[grimar]

Plan to update this in a hour or two, have one testcase failture left. Also changed lot of things.
Generally I must admit that version of Eugene Leviant looks simplier, though our patches has different
purposed..
Mine about redesign in general and can take much longer time to submit (if it will be).
Also it will be even a bit larger after following update.
His patch solves the problem of section order still.
So Eugene, I can still suggest for you to post the patch if you want, and this one can be landed later if you need the feature
you are solving.

[grimar]

• Addressed review comments.
• Reworked the patch. I did a cleanup because found that it is can be written simplier that I tried before.
• Fixed all testcases except one. Unfortunately I was unable to fix the last yet, it is ELF/arm-thumb-interwork-thunk.s, which fails with "Virtual address is not in any segment" llvm error. Since testcase is just about 1.5 week old I had no chance to find the reason quickly. Though I think single testcase should not be major problem for now since it is WIP patch that is subject of change. I will try to fix it as soon I can.

ELF/LinkerScript.cpp

49

Fixed

81

Fixed

282

Fixed, thanks for hint, I did not know about llvm::find_if

[evgeny777]

test/ELF/linkerscript-va.s

10–12

Why were section order and addresses changed?

[grimar]

test/ELF/linkerscript-va.s

10–12

Because section tag is empty here. There is no defined order since all sections just processed as orphans.
Also there is no sorting except by name anymore.
Address changed because there is more PT_LOADs after that sometimes.

That is expected change of this patch, though I think we want to discuss that. I just remember that for previous redesign there were review comments about that we probably want to make user to provide full layout if he/she needs the some exact order. Otherwise it can be changed.

I think FreeBSD script also provides the full layout. Do you have some thoughts about that ?

[emaste]

we probably want to make user to provide full layout if he/she needs the some exact order

Yes, I think it's OK to rely on the user to fully specify the layout if providing a linker script. (And revisit later on if it turns out there's a lot of software that relies on ld/gold defaults for unspecified sections.)

[grimar]

In D19976#486581, @emaste wrote:

we probably want to make user to provide full layout if he/she needs the some exact order

Yes, I think it's OK to rely on the user to fully specify the layout if providing a linker script. (And revisit later on if it turns out there's a lot of software that relies on ld/gold defaults for unspecified sections.)

That sounds good because I guess that implementing heuristic that gold uses for orphans sections not only lead to code complication, but also a bit hard for understanding. I remember I was confused with that fact, I think just strict following of what is written in script is much more simple to understand for users.

[evgeny777]

Can you post a patch then ? I think it is fine to have few visions and chose the most appropriate

Added review
https://reviews.llvm.org/D22455

[evgeny777]

ELF/LinkerScript.cpp

206

Looks like findSection is not called by anyone. I suggest removing it

445–454

This code doesn't sort orphan sections, which might make sense on some occasions.
What is the reason for that?

[grimar]

• Addressed review comments + minor cleanup changes.

ELF/LinkerScript.cpp

206

Right, missed it, removed.

445–454

Because from my understanding we do not need to care about orphans.
I tried to separate the logic of script from anything other as much I could. Just I think it
is easier to process them separatelly.
So since we do not care about orphans, we do not need to sort them.

[grimar]

I am going to simplify and update this in about a day

[grimar]

• Rebased to head.
• Simplified and updated.
• ELF/arm-thumb-interwork-thunk.s is still fails, but that is the only testcase left and I think that is relative to the fact that orphans are not sorted anymore (see few testcases updates because of that also). I am working on fixing that last testcase.

But in general that is in my opinion ok for review, I finished everything I planned.

[grimar]

• Removed unrelated changes.
• Minor changes.

[grimar]

• Was too hurry to remove "unrelated changes", them are needed. Restored.

[grimar]

• Restored previously removed logic of sorting orphans. That allows all testcases to pass without any changes. We might want to remove that later, but I see no harm in that for now and also it fits this design well.

[evgeny777]

Is it any different from https://reviews.llvm.org/D22455 after your changes?

ELF/LinkerScript.cpp

224

You don't need to pass Symtab. You can just use Symtab<ELFT>::X

256

Ditto.

269

I have strong guess, that Rui will ask you to use lambda instead of addSection :)

[grimar]

In D19976#489732, @evgeny777 wrote:

Is it any different from https://reviews.llvm.org/D22455 after your changes?

Not sure I understood the question, though there are lot of.
This one makes LS to be command driven like mentioned in summary.

ScriptConfiguration does not contain any members required for intermediate representation,
just
std::vector<Command> Commands;
which is used when needed to get info from.
It fully separates LS from other parts of linker.

[ruiu]

It seems that this overlaps too much with Eugene's changes. There would be lots of conflicts. It's probably faster if you can split it up in a series of incremental patches and commit them one by one because while it is being review, the base code is being updated.

ELF/LinkerScript.h

38

We shouldn't need an end marker. This struct represents a parsing result of a linker script and basically should form a parse tree. If you need an end marker, it means you are not creating a tree.

[grimar]

ELF/LinkerScript.h

38

Yes, I do not.
CommandKind here is a just plain sequence of commands for parcing.

[grimar]

In D19976#489779, @ruiu wrote:

It seems that this overlaps too much with Eugene's changes. There would be lots of conflicts. It's probably faster if you can split it up in a series of incremental patches and commit them one by one because while it is being review, the base code is being updated.

Ok, let me prepare a first small patch, to see if I understood correctly what you want. I`ll try to prepare it in a next few hours.

[grimar]

In D19976#489838, @grimar wrote:

In D19976#489779, @ruiu wrote:

It seems that this overlaps too much with Eugene's changes. There would be lots of conflicts. It's probably faster if you can split it up in a series of incremental patches and commit them one by one because while it is being review, the base code is being updated.

Ok, let me prepare a first small patch, to see if I understood correctly what you want. I`ll try to prepare it in a next few hours.

I prepared some kind of sample. Rui, could you take a look, is that what you expect to see as a tree ? D22581

[grimar]

Another approach was used finally: D22604

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

 //===- LinkerScript.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_LINKER_SCRIPT_H
 #define LLD_ELF_LINKER_SCRIPT_H
 
+#include "ScriptParser.h"
 #include "Writer.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 {
 
 // 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 ObjectFile;
 template <class ELFT> class OutputSectionBase;
+template <class ELFT> class OutputSectionFactory;
+template <class ELFT> class SymbolTable;
 
-// This class represents each rule in SECTIONS command.
-struct SectionRule {
-  SectionRule(StringRef D, StringRef S)
-      : Dest(D), SectionPattern(S) {}
-
-  StringRef Dest;
-
-  StringRef SectionPattern;
+enum CommandKind {
+  AssignmentKind,
+  OutSectionKind,
+  OutSectionEndKind,
+  InputSectionKind,
+  FillerKind,
+  PhdrsKind,
 };
 
-// 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 };
-
-struct SectionsCommand {
-  SectionsCommandKind Kind;
+struct Command {
+  CommandKind Kind;
   std::vector<StringRef> Expr;
   StringRef Name;
+  StringRef Pattern;
+  bool Keep;
+  std::vector<uint8_t> Filler;
   std::vector<StringRef> Phdrs;
+
+  static Command createAssignmentCmd(std::vector<StringRef> &Expr) {
+    return Command{AssignmentKind, Expr, ".", "", false, {}, {}};
+  }
+  static Command createSymbolAssignmentCmd(std::vector<StringRef> &Expr,
+                                           StringRef Name) {
+    return Command{AssignmentKind, Expr, Name, "", false, {}, {}};
+  }
+  static Command createOutSecCmd(StringRef Name) {
+    return Command{OutSectionKind, {}, Name, "", false, {}, {}};
+  }
+  static Command createOutSecEndCmd() {
+    return Command{OutSectionEndKind, {}, "", "", false, {}, {}};
+  }
+  static Command createInputSectionCmd(StringRef Pattern, bool Keep) {
+    return Command{InputSectionKind, {}, "", Pattern, Keep, {}, {}};
+  }
+  static Command createFillerCmd(const std::vector<uint8_t> &Filler) {
+    return Command{FillerKind, {}, "", "", false, std::move(Filler), {}};
+  }
+  static Command createPhdrsCmd(const std::vector<StringRef> &Phdrs) {
+    return Command{PhdrsKind, {}, "", "", false, {}, std::move(Phdrs)};
+  }
 };
 
 struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;
   bool HasPhdrs;
 };
 
 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
-  // SECTIONS commands.
-  std::vector<SectionRule> Sections;
-
-  // Section fill attribute for each section.
-  llvm::StringMap<std::vector<uint8_t>> Filler;
+  bool DoLayout = false;
 
-  // Used to assign addresses to sections.
-  std::vector<SectionsCommand> Commands;
+  // Used to handle SECTIONS commands for layout.
+  std::vector<Command> Commands;
 
   // Used to assign sections to headers.
-  std::vector<PhdrsCommand> PhdrsCommands;  
-  
-  bool DoLayout = false;
-
+  std::vector<PhdrsCommand> PhdrsCommands;
   llvm::BumpPtrAllocator Alloc;
-
-  // List of section patterns specified with KEEP commands. They will
-  // be kept even if they are unused and --gc-sections is specified.
-  std::vector<StringRef> KeptSections;
 };
 
 extern ScriptConfiguration *ScriptConfig;
 
 // This is a runner of the linker script.
 template <class ELFT> class LinkerScript {
   typedef typename ELFT::uint uintX_t;
+  typedef const std::unique_ptr<elf::ObjectFile<ELFT>> ObjectFile;
 
 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);
   void assignAddresses(ArrayRef<OutputSectionBase<ELFT> *> S);
-  int compareSections(StringRef A, StringRef B);
+
+  std::vector<OutputSectionBase<ELFT> *>
+  createSections(OutputSectionFactory<ELFT> &Factory,
+                 SymbolTable<ELFT> &SymTab);
+
+  void sortSections(std::vector<OutputSectionBase<ELFT> *> &S);
+
   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.
   ScriptConfiguration &Opt = *ScriptConfig;
 
   int getSectionIndex(StringRef Name);
+  void createOutputSection(OutputSectionFactory<ELFT> &Factory,
+                           SymbolTable<ELFT> &Symtab,
+                           std::vector<OutputSectionBase<ELFT> *> &OutList,
+                           size_t Ndx);
+
   std::vector<size_t> getPhdrIndicesForSection(StringRef Name);
 
   uintX_t Dot;
 };
 
 // Variable template is a C++14 feature, so we can't template
 // a global variable. Use a struct to workaround.
 template <class ELFT> struct Script { static LinkerScript<ELFT> *X; };
 template <class ELFT> LinkerScript<ELFT> *Script<ELFT>::X;
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/LinkerScript.cpp

 
 // This is an operator-precedence parser to parse and evaluate
 // a linker script expression. For each linker script arithmetic
 // expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
 // is created and ran.
 namespace {
 class ExprParser : public ScriptParserBase {
 public:
   ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
       : ScriptParserBase(Tokens), Dot(Dot) {}
 
   uint64_t run();
 
 private:
   uint64_t parsePrimary();
   uint64_t parseTernary(uint64_t Cond);
   uint64_t apply(StringRef Op, uint64_t L, uint64_t R);
return StringSwitch<int>(Op)
       .Case(">=", 2)
       .Case("<=", 2)
       .Case("==", 2)
       .Case("!=", 2)
       .Case("&", 1)
       .Default(-1);
 }
 
 static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
   return ExprParser(Tokens, Dot).run();
 }
 
 uint64_t ExprParser::run() {
   uint64_t V = parseExpr();
   if (!atEOF() && !Error)
     setError("stray token: " + peek());
   return V;
uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
   }
   return Lhs;
 }
 
 // Reads and evaluates an arithmetic expression.
 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
 
 template <class ELFT>
-StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
-  for (SectionRule &R : Opt.Sections)
-    if (globMatch(R.SectionPattern, S->getSectionName()))
-      return R.Dest;
-  return "";
+bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
+  if (!Opt.DoLayout)
+    return false;
+  for (const Command &Cmd : Opt.Commands) {
+    if (Cmd.Kind != InputSectionKind)
+      continue;
+    if (!Cmd.Keep)
+      continue;
+    if (globMatch(Cmd.Pattern, S->getSectionName()))
+      return true;
+  }
+  return false;
 }
 
 template <class ELFT>
-bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
-  return getOutputSection(S) == "/DISCARD/";
+static void addSection(OutputSectionFactory<ELFT> &Factory,
+                       StringRef OutSecName, InputSectionBase<ELFT> *InSec,
+                       std::vector<OutputSectionBase<ELFT> *> &OutList) {
+  if (OutSecName == "/DISCARD/") {
+    InSec->Live = false;
+    return;
+  }
+
+  OutputSectionBase<ELFT> *OutSection = nullptr;
+  bool IsNew;
+  std::tie(OutSection, IsNew) = Factory.create(InSec, OutSecName);
+  OutSection->addSection(InSec);
+  if (IsNew)
+    OutList.push_back(OutSection);
 }
 
 template <class ELFT>
-bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
-  for (StringRef Pat : Opt.KeptSections)
-    if (globMatch(Pat, S->getSectionName()))
-      return true;
-  return false;
+void LinkerScript<ELFT>::createOutputSection(
+    OutputSectionFactory<ELFT> &Factory, SymbolTable<ELFT> &Symtab,
+    std::vector<OutputSectionBase<ELFT> *> &OutList, size_t Ndx) {
+  std::vector<uint8_t> *Filler = nullptr;
+
+  size_t SecNum = OutList.size();
+  for (size_t I = Ndx, E = Opt.Commands.size(); I < E; ++I) {
+    Command &Cmd = Opt.Commands[I];
+    if (Cmd.Kind == OutSectionEndKind)
+      break;
+
+    if (Cmd.Kind == FillerKind) {
+      Filler = &Cmd.Filler;
+      continue;
+    }
+
+    if (Cmd.Kind != InputSectionKind)
+      continue;
+
+    for (ObjectFile &F : Symtab.getObjectFiles())
+      for (InputSectionBase<ELFT> *C : F->getSections())
+        if (!isDiscarded(C) && !C->OutSec)
+          if (globMatch(Cmd.Pattern, C->getSectionName()))
+            addSection(Factory, Opt.Commands[Ndx].Name, C, OutList);
+  }
+
+  for (size_t I = SecNum; I < OutList.size(); ++I)
+    OutList[I]->Filler = Filler;
 }
 
 template <class ELFT>
-void LinkerScript<ELFT>::assignAddresses(
-    ArrayRef<OutputSectionBase<ELFT> *> Sections) {
+std::vector<OutputSectionBase<ELFT> *>
+LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory,
+                                   SymbolTable<ELFT> &Symtab) {
+  std::vector<OutputSectionBase<ELFT> *> Sections;
+  for (size_t I = 0, E = Opt.Commands.size(); I != E; ++I)
+    if (Opt.Commands[I].Kind == OutSectionKind)
+      createOutputSection(Factory, Symtab, Sections, I);
+
   // 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) {
-    StringRef Name = Sec->getName();
-    if (getSectionIndex(Name) == INT_MAX)
-      Opt.Commands.push_back({SectionKind, {}, Name, {}});
-  }
+  for (ObjectFile &F : Symtab.getObjectFiles())
+    for (InputSectionBase<ELFT> *C : F->getSections())
+      if (!isDiscarded(C) && !C->OutSec)
+        addSection(Factory, getOutputSectionName(C), C, Sections);
+
+  return Sections;
 
+template <class ELFT>
+void LinkerScript<ELFT>::assignAddresses(
+    ArrayRef<OutputSectionBase<ELFT> *> Sections) {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
   uintX_t ThreadBssOffset = 0;
+  DenseSet<OutputSectionBase<ELFT> *> Assigned;
+
+  auto setVA = [&](OutputSectionBase<ELFT> *Sec) {
+    if (!Sec)
+      return;
+
+    if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
+      uintX_t TVA = Dot + ThreadBssOffset;
+      TVA = alignTo(TVA, Sec->getAlignment());
+      Sec->setVA(TVA);
+      ThreadBssOffset = TVA - Dot + Sec->getSize();
+      Assigned.insert(Sec);
+      return;
+    }
+
+    if (Sec->getFlags() & SHF_ALLOC) {
+      Dot = alignTo(Dot, Sec->getAlignment());
+      Sec->setVA(Dot);
+      MinVA = std::min(MinVA, Dot);
+      Dot += Sec->getSize();
+      Assigned.insert(Sec);
+      return;
+    }
+  };
 
-  for (SectionsCommand &Cmd : Opt.Commands) {
+  for (const Command &Cmd : Opt.Commands) {
     if (Cmd.Kind == AssignmentKind) {
       uint64_t Val = evalExpr(Cmd.Expr, Dot);
 
       if (Cmd.Name == ".") {
         Dot = Val;
       } else {
         auto *D = cast<DefinedRegular<ELFT>>(Symtab<ELFT>::X->find(Cmd.Name));
         D->Value = Val;
       }
       continue;
     }
 
+    if (Cmd.Kind != OutSectionKind)
+      continue;
+
     // Find all the sections with required name. There can be more than
     // one section with such name, if the alignment, flags or type
     // attribute differs.
-    assert(Cmd.Kind == SectionKind);
     for (OutputSectionBase<ELFT> *Sec : Sections) {
       if (Sec->getName() != Cmd.Name)
         continue;
-
-      if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
-        uintX_t TVA = Dot + ThreadBssOffset;
-        TVA = alignTo(TVA, Sec->getAlignment());
-        Sec->setVA(TVA);
-        ThreadBssOffset = TVA - Dot + Sec->getSize();
-        continue;
-      }
-
-      if (Sec->getFlags() & SHF_ALLOC) {
-        Dot = alignTo(Dot, Sec->getAlignment());
-        Sec->setVA(Dot);
-        MinVA = std::min(MinVA, Dot);
-        Dot += Sec->getSize();
-        continue;
-      }
+      setVA(Sec);
     }
   }
 
+  // Finally process all orphan sections.
+  for (OutputSectionBase<ELFT> *Sec : Sections)
+    if (!Assigned.count(Sec))
+      setVA(Sec);
+
   // ELF and Program headers need to be right before the first section in
   // memory. Set their addresses accordingly.
   MinVA = alignDown(MinVA - Out<ELFT>::ElfHeader->getSize() -
                         Out<ELFT>::ProgramHeaders->getSize(),
                     Target->PageSize);
   Out<ELFT>::ElfHeader->setVA(MinVA);
   Out<ELFT>::ProgramHeaders->setVA(Out<ELFT>::ElfHeader->getSize() + MinVA);
 }
for (OutputSectionBase<ELFT> *Sec : Sections) {
     if (RelroNum != -1 && isRelroSection(Sec))
       Phdrs[RelroNum].AddSec(Sec);
     if (NoteNum != -1 && Sec->getType() == SHT_NOTE)
       Phdrs[NoteNum].AddSec(Sec);
   }
   return Phdrs;
 }
 
-template <class ELFT>
-ArrayRef<uint8_t> LinkerScript<ELFT>::getFiller(StringRef Name) {
-  auto I = Opt.Filler.find(Name);
-  if (I == Opt.Filler.end())
-    return {};
-  return I->second;
-}
-
 // Returns the index of the given section name in linker script
 // SECTIONS commands. Sections are laid out as the same order as they
 // were in the script. If a given name did not appear in the script,
 // it returns INT_MAX, so that it will be laid out at end of file.
-template <class ELFT>
-int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
+template <class ELFT> int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
   auto Begin = Opt.Commands.begin();
   auto End = Opt.Commands.end();
-  auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
-    return N.Kind == SectionKind && N.Name == Name;
+  auto I = std::find_if(Begin, End, [&](Command &N) {
+    return N.Kind == OutSectionKind && N.Name == Name;
   });
   return I == End ? INT_MAX : (I - Begin);
 }
 
-// A compartor to sort output sections. Returns -1 or 1 if
-// A or B are mentioned in linker script. Otherwise, returns 0.
 template <class ELFT>
-int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
-  int I = getSectionIndex(A);
-  int J = getSectionIndex(B);
+void LinkerScript<ELFT>::sortSections(
+    std::vector<OutputSectionBase<ELFT> *> &S) {
+  std::stable_sort(S.begin(), S.end(), [this](OutputSectionBase<ELFT> *A,
+                                              OutputSectionBase<ELFT> *B) {
+    int I = getSectionIndex(A->getName());
+    int J = getSectionIndex(B->getName());
     if (I == INT_MAX && J == INT_MAX)
-    return 0;
-  return I < J ? -1 : 1;
+      return false;
+    return I < J;
+  });
 }
 
-template <class ELFT>
-void LinkerScript<ELFT>::addScriptedSymbols() {
-  for (SectionsCommand &Cmd : Opt.Commands)
+template <class ELFT> void LinkerScript<ELFT>::addScriptedSymbols() {
+  if (!Opt.DoLayout)
+    return;
+  for (Command &Cmd : Opt.Commands)
     if (Cmd.Kind == AssignmentKind)
-      if (Cmd.Name != "." && Symtab<ELFT>::X->find(Cmd.Name) == nullptr)
+      if (Cmd.Name != ".")
         Symtab<ELFT>::X->addAbsolute(Cmd.Name, STV_DEFAULT);
 }
 
 template <class ELFT> bool LinkerScript<ELFT>::hasPhdrsCommands() {
   return !Opt.PhdrsCommands.empty();
 }
 
 // Returns indices of ELF headers containing specific section, identified
 // by Name. Each index is a zero based number of ELF header listed within
 // PHDRS {} script block.
 template <class ELFT>
 std::vector<size_t>
 LinkerScript<ELFT>::getPhdrIndicesForSection(StringRef Name) {
+  auto I = llvm::find_if(Opt.Commands, [&](Command &Cmd) {
+    return Cmd.Kind == OutSectionKind && Cmd.Name == Name;
+  });
+
+  if (I == Opt.Commands.end())
+    return {};
+
+  ++I;
+  while (I != Opt.Commands.end()) {
+    Command &Cmd = *I;
+    if (Cmd.Kind == OutSectionEndKind)
+      return {};
+
+    if (Cmd.Kind != PhdrsKind) {
+      ++I;
+      continue;
+    }
+
     std::vector<size_t> Indices;
-  auto ItSect = std::find_if(
-      Opt.Commands.begin(), Opt.Commands.end(),
-      [Name](const SectionsCommand &Cmd) { return Cmd.Name == Name; });
-  if (ItSect != Opt.Commands.end()) {
-    SectionsCommand &SecCmd = (*ItSect);
-    for (StringRef PhdrName : SecCmd.Phdrs) {
+    for (StringRef PhdrName : Cmd.Phdrs) {
       auto ItPhdr = std::find_if(
           Opt.PhdrsCommands.rbegin(), Opt.PhdrsCommands.rend(),
           [PhdrName](PhdrsCommand &Cmd) { return Cmd.Name == PhdrName; });
       if (ItPhdr == Opt.PhdrsCommands.rend())
         error("section header '" + PhdrName + "' is not listed in PHDRS");
       else
         Indices.push_back(std::distance(ItPhdr, Opt.PhdrsCommands.rend()) - 1);
     }
-  }
     return Indices;
   }
 
+  return {};
+}
+
 class elf::ScriptParser : public ScriptParserBase {
   typedef void (ScriptParser::*Handler)();
 
 public:
   ScriptParser(StringRef S, bool B) : ScriptParserBase(S), IsUnderSysroot(B) {}
 
   void run();
 

 
 void ScriptParser::readLocationCounterValue() {
   expect(".");
   expect("=");
   std::vector<StringRef> Expr = readSectionsCommandExpr();
   if (Expr.empty())
     error("error in location counter expression");
   else
-    Opt.Commands.push_back({AssignmentKind, std::move(Expr), ".", {}});
+    Opt.Commands.push_back(Command::createAssignmentCmd(Expr));
 }
 
 void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
-  Opt.Commands.push_back({SectionKind, {}, OutSec, {}});
-  SectionsCommand &Cmd = Opt.Commands.back();
+  Opt.Commands.push_back(Command::createOutSecCmd(OutSec));
   expect(":");
   expect("{");
 
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
       expect("(");
       while (!Error && !skip(")"))
-        Opt.Sections.emplace_back(OutSec, next());
+        Opt.Commands.push_back(Command::createInputSectionCmd(next(), false));
     } else if (Tok == "KEEP") {
       expect("(");
       expect("*");
       expect("(");
-      while (!Error && !skip(")")) {
-        StringRef Sec = next();
-        Opt.Sections.emplace_back(OutSec, Sec);
-        Opt.KeptSections.push_back(Sec);
-      }
+      while (!Error && !skip(")"))
+        Opt.Commands.push_back(Command::createInputSectionCmd(next(), true));
       expect(")");
     } else {
       setError("unknown command " + Tok);
     }
   }
-  Cmd.Phdrs = readOutputSectionPhdrs();
+
+  std::vector<StringRef> Phdrs = readOutputSectionPhdrs();
+  if (!Phdrs.empty())
+    Opt.Commands.push_back(Command::createPhdrsCmd(Phdrs));
+
+  if (Error)
+    return;
 
   StringRef Tok = peek();
   if (Tok.startswith("=")) {
     if (!Tok.startswith("=0x")) {
       setError("filler should be a hexadecimal value");
       return;
     }
     Tok = Tok.substr(3);
-    Opt.Filler[OutSec] = parseHex(Tok);
     next();
+    Opt.Commands.push_back(Command::createFillerCmd(parseHex(Tok)));
   }
+
+  Opt.Commands.push_back(Command::createOutSecEndCmd());
 }
 
 void ScriptParser::readSymbolAssignment(StringRef Name) {
   expect("=");
   std::vector<StringRef> Expr = readSectionsCommandExpr();
   if (Expr.empty())
     error("error in symbol assignment expression");
   else
-    Opt.Commands.push_back({AssignmentKind, std::move(Expr), Name, {}});
+    Opt.Commands.push_back(Command::createSymbolAssignmentCmd(Expr, Name));
 }
 
 std::vector<StringRef> ScriptParser::readSectionsCommandExpr() {
   std::vector<StringRef> Expr;
   while (!Error) {
     StringRef Tok = next();
     if (Tok == ";")
       break;

ELF/OutputSections.h

public:
   bool PageAlign = false;
 
   virtual void finalize() {}
   virtual void finalizePieces() {}
   virtual void assignOffsets() {}
   virtual void writeTo(uint8_t *Buf) {}
   virtual ~OutputSectionBase() = default;
 
+  std::vector<uint8_t> *Filler = nullptr;
+
 protected:
   StringRef Name;
   Elf_Shdr Header;
 };
 
 template <class ELFT> class GotSection final : public OutputSectionBase<ELFT> {
   typedef OutputSectionBase<ELFT> Base;
   typedef typename ELFT::uint uintX_t;
template <class ELFT> class OutputSectionFactory {
   typedef typename elf::SectionKey<ELFT::Is64Bits> Key;
 
 public:
   std::pair<OutputSectionBase<ELFT> *, bool> create(InputSectionBase<ELFT> *C,
                                                     StringRef OutsecName);
 
   OutputSectionBase<ELFT> *lookup(StringRef Name, uint32_t Type, uintX_t Flags);
 
 private:
   Key createKey(InputSectionBase<ELFT> *C, StringRef OutsecName);
 
   llvm::SmallDenseMap<Key, OutputSectionBase<ELFT> *> Map;
 };
 
 template <class ELFT> BuildIdSection<ELFT> *Out<ELFT>::BuildId;
 template <class ELFT> DynamicSection<ELFT> *Out<ELFT>::Dynamic;
 template <class ELFT> EhFrameHeader<ELFT> *Out<ELFT>::EhFrameHdr;

 
 } // namespace elf
 } // namespace lld
 
 namespace llvm {
 template <bool Is64Bits> struct DenseMapInfo<lld::elf::SectionKey<Is64Bits>> {
   typedef typename lld::elf::SectionKey<Is64Bits> Key;
 
   static Key getEmptyKey();
   static Key getTombstoneKey();
   static unsigned getHashValue(const Key &Val);
   static bool isEqual(const Key &LHS, const Key &RHS);
 };
 }
 
 #endif

ELF/OutputSections.cpp

 static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
   size_t I = 0;
   for (; I + A.size() < Size; I += A.size())
     memcpy(Buf + I, A.data(), A.size());
   memcpy(Buf + I, A.data(), Size - I);
 }
 
 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
-  ArrayRef<uint8_t> Filler = Script<ELFT>::X->getFiller(this->Name);
-  if (!Filler.empty())
-    fill(Buf, this->getSize(), Filler);
+  if (Filler)
+    fill(Buf, this->getSize(), *Filler);
   if (Config->Threads) {
     parallel_for_each(Sections.begin(), Sections.end(),
                       [=](InputSection<ELFT> *C) { C->writeTo(Buf); });
   } else {
     for (InputSection<ELFT> *C : Sections)
       C->writeTo(Buf);
   }
 }

ELF/Writer.cpp

public:
   Writer(SymbolTable<ELFT> &S) : Symtab(S) {}
   void run();
 
 private:
   typedef PhdrEntry<ELFT> Phdr;
 
   void copyLocalSymbols();
   void addReservedSymbols();
+
+  std::vector<OutputSectionBase<ELFT> *>
+  createRegularSections(OutputSectionFactory<ELFT> &Factory);
   void createSections();
+
   void addPredefinedSections();
   bool needsGot();
 
   void createPhdrs();
   void assignAddresses();
   void assignFileOffsets();
   void setPhdrs();
   void fixHeaders();
private:
 
   uintX_t FileSize;
   uintX_t SectionHeaderOff;
 };
 } // anonymous namespace
 
 template <class ELFT>
 StringRef elf::getOutputSectionName(InputSectionBase<ELFT> *S) {
-  StringRef Dest = Script<ELFT>::X->getOutputSection(S);
-  if (!Dest.empty())
-    return Dest;
-
   StringRef Name = S->getSectionName();
   for (StringRef V : {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.",
                       ".init_array.", ".fini_array.", ".ctors.", ".dtors.",
                       ".tbss.", ".gcc_except_table.", ".tdata."})
     if (Name.startswith(V))
       return V.drop_back();
   return Name;
 }
 
 template <class ELFT>
 void elf::reportDiscarded(InputSectionBase<ELFT> *IS,
                           const std::unique_ptr<elf::ObjectFile<ELFT>> &File) {
   if (!Config->PrintGcSections || !IS || IS->Live)
     return;
   errs() << "removing unused section from '" << IS->getSectionName()
          << "' in file '" << File->getName() << "'\n";
 }
 
 template <class ELFT> void elf::writeResult(SymbolTable<ELFT> *Symtab) {
   typedef typename ELFT::uint uintX_t;
   typedef typename ELFT::Ehdr Elf_Ehdr;
 
   // Create singleton output sections.
   OutputSection<ELFT> Bss(".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE);
   DynamicSection<ELFT> Dynamic;
   EhOutputSection<ELFT> EhFrame;
   GotSection<ELFT> Got;

 }
 
 // Output section ordering is determined by this function.
 template <class ELFT>
 static bool compareSections(OutputSectionBase<ELFT> *A,
                             OutputSectionBase<ELFT> *B) {
   typedef typename ELFT::uint uintX_t;
 
-  int Comp = Script<ELFT>::X->compareSections(A->getName(), B->getName());
-  if (Comp != 0)
-    return Comp < 0;
-
   uintX_t AFlags = A->getFlags();
   uintX_t BFlags = B->getFlags();
 
   // Allocatable sections go first to reduce the total PT_LOAD size and
   // so debug info doesn't change addresses in actual code.
   bool AIsAlloc = AFlags & SHF_ALLOC;
   bool BIsAlloc = BFlags & SHF_ALLOC;
   if (AIsAlloc != BIsAlloc)

 }
 
 // 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() {
+template <class ELFT>
+std::vector<OutputSectionBase<ELFT> *>
+Writer<ELFT>::createRegularSections(OutputSectionFactory<ELFT> &Factory) {
+  if (ScriptConfig->DoLayout)
+    return Script<ELFT>::X->createSections(Factory, Symtab);
+
   // 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) {
-        OwningSections.emplace_back(Sec);
-        OutputSections.push_back(Sec);
+      if (IsNew)
         RegularSections.push_back(Sec);
-      }
+
       Sec->addSection(C);
     }
   }
+  return RegularSections;
+}
+
+// Create output section objects and add them to OutputSections.
+template <class ELFT> void Writer<ELFT>::createSections() {
+  OutputSectionFactory<ELFT> Factory;
+  std::vector<OutputSectionBase<ELFT> *> RegularSections =
+      createRegularSections(Factory);
+  for (OutputSectionBase<ELFT> *Sec : RegularSections) {
+    OwningSections.emplace_back(Sec);
+    OutputSections.push_back(Sec);
+  }
 
   // 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);
if (HasError)
     return;
 
   addCommonSymbols(CommonSymbols);
 
   // So far we have added sections from input object files.
   // This function adds linker-created Out<ELFT>::* sections.
   addPredefinedSections();
 
+  if (ScriptConfig->DoLayout)
+    Script<ELFT>::X->sortSections(OutputSections);
+  else
     std::stable_sort(OutputSections.begin(), OutputSections.end(),
                      compareSections<ELFT>);
 
   unsigned I = 1;
   for (OutputSectionBase<ELFT> *Sec : OutputSections) {
     Sec->SectionIndex = I++;
     Sec->setSHName(Out<ELFT>::ShStrTab->addString(Sec->getName()));
   }
 
   // Finalizers fix each section's size.

 
 // This function add Out<ELFT>::* sections to OutputSections.
 template <class ELFT> void Writer<ELFT>::addPredefinedSections() {
   auto Add = [&](OutputSectionBase<ELFT> *C) {
     if (C)
       OutputSections.push_back(C);
   };
 
   // A core file does not usually contain unmodified segments except
   // the first page of the executable. Add the build ID section to beginning of
   // the file so that the section is included in the first page.
   if (Out<ELFT>::BuildId)
     OutputSections.insert(OutputSections.begin(), Out<ELFT>::BuildId);
 
   // Add .interp at first because some loaders want to see that section
   // on the first page of the executable file when loaded into memory.
   if (needsInterpSection<ELFT>())
     OutputSections.insert(OutputSections.begin(), Out<ELFT>::Interp);
 
   // This order is not the same as the final output order
   // because we sort the sections using their attributes below.

test/ELF/linkerscript-sections-keep.s

 # RUN: echo "SECTIONS { \
 # RUN:  .keep : { KEEP(*(.keep)) } \
 # RUN:  .nokeep : { *(.keep) }}" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix=MIXED1 %s
 # MIXED1:      Sections:
 # MIXED1-NEXT: Idx Name          Size      Address         Type
 # MIXED1-NEXT:   0               00000000 0000000000000000
-# MIXED1-NEXT:   1 .keep         00000004 0000000000000120 DATA
-# MIXED1-NEXT:   2 .temp         00000004 0000000000000124 DATA
-# MIXED1-NEXT:   3 .text         00000007 0000000000000128 TEXT DATA
+# MIXED1-NEXT:   1 .keep         00000004 0000000000000158 DATA
+# MIXED1-NEXT:   2 .text         00000007 000000000000015c TEXT DATA
+# MIXED1-NEXT:   3 .temp         00000004 0000000000000163 DATA
 # MIXED1-NEXT:   4 .symtab       00000060 0000000000000000
 # MIXED1-NEXT:   5 .shstrtab     0000002d 0000000000000000
 # MIXED1-NEXT:   6 .strtab       00000012 0000000000000000
 
 ## The same, but now section without KEEP is at first place.
 ## gold and bfd linkers disagree here. gold collects .keep while
 ## bfd keeps it. Our current behavior is compatible with bfd although
 ## we can choose either way.
 # RUN: echo "SECTIONS { \
 # RUN:  .nokeep : { *(.keep) } \
 # RUN:  .keep : { KEEP(*(.keep)) }}" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix=MIXED2 %s
 # MIXED2:      Sections:
 # MIXED2-NEXT: Idx Name          Size      Address         Type
 # MIXED2-NEXT:   0               00000000 0000000000000000
-# MIXED2-NEXT:   1 .nokeep       00000004 0000000000000120 DATA
-# MIXED2-NEXT:   2 .temp         00000004 0000000000000124 DATA
-# MIXED2-NEXT:   3 .text         00000007 0000000000000128 TEXT DATA
+# MIXED2-NEXT:   1 .nokeep       00000004 0000000000000158 DATA
+# MIXED2-NEXT:   2 .text         00000007 000000000000015c TEXT DATA
+# MIXED2-NEXT:   3 .temp         00000004 0000000000000163 DATA
 # MIXED2-NEXT:   4 .symtab       00000060 0000000000000000
 # MIXED2-NEXT:   5 .shstrtab     0000002f 0000000000000000
 # MIXED2-NEXT:   6 .strtab       00000012 0000000000000000
 
 .global _start
 _start:
  mov temp, %eax
 
 .section .keep, "a"
 keep:
  .long 1
 
 .section .temp, "a"
 temp:
  .long 2

test/ELF/linkerscript-sections.s

 # RUN: ld.lld -o %t2 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t2 | \
 # RUN:   FileCheck -check-prefix=SEC-DEFAULT %s
 
 #             Idx Name          Size
 # SEC-DEFAULT: 1 .text         0000000e {{[0-9a-f]*}} TEXT DATA
 # SEC-DEFAULT: 2 .data         00000020 {{[0-9a-f]*}} DATA
 # SEC-DEFAULT: 3 other         00000003 {{[0-9a-f]*}} DATA
-# SEC-DEFAULT: 4 .bss          00000002 {{[0-9a-f]*}} BSS
-# SEC-DEFAULT: 5 .shstrtab     00000002 {{[0-9a-f]*}}
+# SEC-DEFAULT: 4 .shstrtab     00000002 {{[0-9a-f]*}}
+# SEC-DEFAULT: 5 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-DEFAULT: 6 .symtab       00000030 {{[0-9a-f]*}}
 # SEC-DEFAULT: 7 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-DEFAULT: 8 .strtab       00000008 {{[0-9a-f]*}}
 
 # Sections are put in order specified in linker script.
 # RUN: echo "SECTIONS { \
 # RUN:          .bss : { *(.bss) } \
 # RUN:          other : { *(other) } \

 # RUN: ld.lld -o %t4 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t4 | \
 # RUN:   FileCheck -check-prefix=SEC-SWAP-NAMES %s
 
 #                Idx Name          Size
 # SEC-SWAP-NAMES: 1 .data         0000000e {{[0-9a-f]*}} TEXT DATA
 # SEC-SWAP-NAMES: 2 .text         00000020 {{[0-9a-f]*}} DATA
 # SEC-SWAP-NAMES: 3 other         00000003 {{[0-9a-f]*}} DATA
-# SEC-SWAP-NAMES: 4 .bss          00000002 {{[0-9a-f]*}} BSS
-# SEC-SWAP-NAMES: 5 .shstrtab     00000002 {{[0-9a-f]*}}
+# SEC-SWAP-NAMES: 4 .shstrtab     00000002 {{[0-9a-f]*}}
+# SEC-SWAP-NAMES: 5 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-SWAP-NAMES: 6 .symtab       00000030 {{[0-9a-f]*}}
 # SEC-SWAP-NAMES: 7 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-SWAP-NAMES: 8 .strtab       00000008 {{[0-9a-f]*}}
 
 # .shstrtab from the input object file is discarded.
 # RUN: echo "SECTIONS { \
 # RUN:          /DISCARD/ : { *(.shstrtab) } }" > %t.script
 # RUN: ld.lld -o %t5 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t5 | \
 # RUN:   FileCheck -check-prefix=SEC-DISCARD %s
 
 #             Idx Name          Size
 # SEC-DISCARD: 1 .text         0000000e {{[0-9a-f]*}} TEXT DATA
 # SEC-DISCARD: 2 .data         00000020 {{[0-9a-f]*}} DATA
 # SEC-DISCARD: 3 other         00000003 {{[0-9a-f]*}} DATA
 # SEC-DISCARD: 4 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-DISCARD: 5 .symtab       00000030 {{[0-9a-f]*}}
 # SEC-DISCARD: 6 .shstrtab     00000032 {{[0-9a-f]*}}
 # SEC-DISCARD: 7 .strtab       00000008 {{[0-9a-f]*}}
 
-# Multiple SECTIONS command specifying additional input section descriptions
-# for the same output section description - input sections are merged into
-# one output section.
-# RUN: echo "SECTIONS { \
-# RUN:          .text : { *(.text) } \
-# RUN:          .data : { *(.data) } } \
-# RUN:       SECTIONS { \
-# RUN:          .data : { *(other) } }" > %t.script
-# RUN: ld.lld -o %t6 --script %t.script %t
-# RUN: llvm-objdump -section-headers %t6 | \
-# RUN:   FileCheck -check-prefix=SEC-MULTI %s
-
-#           Idx Name          Size
-# SEC-MULTI: 1 .text         0000000e {{[0-9a-f]*}} TEXT DATA
-# SEC-MULTI: 2 .data         00000023 {{[0-9a-f]*}} DATA
-# SEC-MULTI: 3 .bss          00000002 {{[0-9a-f]*}} BSS
-# SEC-MULTI: 4 .shstrtab     00000002 {{[0-9a-f]*}}
-# SEC-MULTI: 5 .symtab       00000030 {{[0-9a-f]*}}
-# SEC-MULTI: 6 .shstrtab     0000002c {{[0-9a-f]*}}
-# SEC-MULTI: 7 .strtab       00000008 {{[0-9a-f]*}}
-
 .globl _start
 _start:
     mov $60, %rax
     mov $42, %rdi
 
 .section .data,"aw"
 .quad 10, 10, 20, 20
 .section other,"aw"
 .short 10
 .byte 20
 .section .shstrtab,""
 .short 20
 .section .bss,"",@nobits
 .short 0

test/ELF/linkerscript-va.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 # RUN: echo "SECTIONS {}" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck %s
 # CHECK:      Sections:
 # CHECK-NEXT: Idx Name          Size      Address          Type
 # CHECK-NEXT:   0               00000000 0000000000000000
-# CHECK-NEXT:   1 .foo          00000004 0000000000000120 DATA
-# CHECK-NEXT:   2 .boo          00000004 0000000000000124 DATA
-# CHECK-NEXT:   3 .text         00000001 0000000000000128 TEXT DATA
+# CHECK-NEXT:   1 .text         00000001 0000000000000158 TEXT DATA
+# CHECK-NEXT:   2 .foo          00000004 0000000000000159 DATA
+# CHECK-NEXT:   3 .boo          00000004 000000000000015d DATA
 
 .global _start
 _start:
  nop
 
 .section .foo, "a"
 foo:
  .long 0
 
 .section .boo, "a"
 boo:
  .long 0