Index: ELF/LinkerScript.h
===================================================================
--- ELF/LinkerScript.h
+++ ELF/LinkerScript.h
@@ -10,11 +10,13 @@
 #ifndef LLD_ELF_LINKER_SCRIPT_H
 #define LLD_ELF_LINKER_SCRIPT_H
 
+#include "ScriptParser.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"
+#include <functional>
 
 namespace lld {
 namespace elf {
@@ -24,48 +26,19 @@
 void readLinkerScript(MemoryBufferRef MB);
 
 class ScriptParser;
+class LayoutParser;
 template <class ELFT> class InputSectionBase;
+template <class ELFT> class ObjectFile;
 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 { ExprKind, SectionKind };
-
-struct SectionsCommand {
-  SectionsCommandKind Kind;
-  std::vector<StringRef> Expr;
-  StringRef SectionName;
-};
+template <class ELFT> class OutputSectionFactory;
+template <class ELFT> class SymbolTable;
 
 // 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;
-
-  // Used to assign addresses to sections.
-  std::vector<SectionsCommand> Commands;
-
   bool DoLayout = false;
+  StringRef SectionsData;
 
   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;
@@ -75,19 +48,19 @@
   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);
   void assignAddresses(ArrayRef<OutputSectionBase<ELFT> *> S);
-  int compareSections(StringRef A, StringRef B);
+
+  std::vector<OutputSectionBase<ELFT> *>
+  createSections(OutputSectionFactory<ELFT> &Factory,
+                 SymbolTable<ELFT> &SymTab);
+
+  void checkLive(std::vector<InputSectionBase<ELFT> *> &Sec,
+                 std::function<void(InputSectionBase<ELFT> *)> MarkFn);
 
 private:
   // "ScriptConfig" is a bit too long, so define a short name for it.
   ScriptConfiguration &Opt = *ScriptConfig;
 
-  int getSectionIndex(StringRef Name);
-
   uintX_t Dot;
 };
 
Index: ELF/LinkerScript.cpp
===================================================================
--- ELF/LinkerScript.cpp
+++ ELF/LinkerScript.cpp
@@ -20,6 +20,7 @@
 #include "OutputSections.h"
 #include "ScriptParser.h"
 #include "SymbolTable.h"
+#include "Writer.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/ELF.h"
 #include "llvm/Support/FileSystem.h"
@@ -44,7 +45,7 @@
 namespace {
 class ExprParser : public ScriptParserBase {
 public:
-  ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
+  ExprParser(const std::vector<StringRef> &Tokens, uint64_t Dot)
       : ScriptParserBase(Tokens), Dot(Dot) {}
 
   uint64_t run();
@@ -76,7 +77,7 @@
       .Default(-1);
 }
 
-static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
+static uint64_t evalExpr(const std::vector<StringRef> &Tokens, uint64_t Dot) {
   return ExprParser(Tokens, Dot).run();
 }
 
@@ -186,27 +187,6 @@
 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
 
 template <class ELFT>
-StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
-  for (SectionRule &R : Opt.Sections)
-    if (matchStr(R.SectionPattern, S->getSectionName()))
-      return R.Dest;
-  return "";
-}
-
-template <class ELFT>
-bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
-  return getOutputSection(S) == "/DISCARD/";
-}
-
-template <class ELFT>
-bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
-  for (StringRef Pat : Opt.KeptSections)
-    if (matchStr(Pat, S->getSectionName()))
-      return true;
-  return false;
-}
-
-template <class ELFT>
 static OutputSectionBase<ELFT> *
 findSection(ArrayRef<OutputSectionBase<ELFT> *> V, StringRef Name) {
   for (OutputSectionBase<ELFT> *Sec : V)
@@ -215,82 +195,242 @@
   return nullptr;
 }
 
+enum CommandKind {
+  ExprKind,
+  OutSectionKind,
+  InputSectionKind,
+  FillerKind,
+};
+
+struct Command {
+  CommandKind Kind;
+  std::vector<StringRef> Expr;
+  StringRef Name;
+  StringRef Pattern;
+  bool Keep;
+  std::vector<uint8_t> Filler;
+
+  static Command createExprCmd(std::vector<StringRef> &Expr) {
+    return Command{ExprKind, Expr, "", "", false, {}};
+  }
+  static Command createOutSecCmd(StringRef Name) {
+    return Command{OutSectionKind, {}, Name, "", false, {}};
+  }
+  static Command createInputSectionCmd(StringRef Pattern, bool Keep) {
+    return Command{InputSectionKind, {}, "", Pattern, Keep, {}};
+  }
+  static Command createFillerCmd(std::vector<uint8_t> &Filler) {
+    return Command{FillerKind, {}, "", "", false, std::move(Filler)};
+  }
+};
+
+class elf::LayoutParser : public ScriptParserBase {
+  typedef std::function<void(const Command &Cmd)> Callback;
+
+public:
+  LayoutParser() : ScriptParserBase(ScriptConfig->SectionsData) {}
+
+  size_t run(Callback C) {
+    expect("SECTIONS");
+    expect("{");
+    while (!Error && !skip("}")) {
+      StringRef Tok = peek();
+      if (Tok == ".")
+        parseLocationCounterValue(C);
+      else
+        parseOutputSectionDescription(C);
+    }
+    return Pos - 1;
+  }
+
+private:
+  void parseLocationCounterValue(Callback Call) {
+    expect(".");
+    expect("=");
+
+    std::vector<StringRef> Expr;
+    while (!Error) {
+      StringRef Tok = next();
+      if (Tok == ";")
+        break;
+      Expr.push_back(Tok);
+    }
+    if (Expr.empty())
+      error("error in location counter expression");
+    Call(Command::createExprCmd(Expr));
+  }
+
+  void parseOutputSectionDescription(Callback Call) {
+    StringRef OutSec = next();
+    Call(Command::createOutSecCmd(OutSec));
+    expect(":");
+    expect("{");
+
+    while (!Error && !skip("}")) {
+      StringRef Tok = next();
+      if (Tok == "*") {
+        expect("(");
+        while (!Error && !skip(")"))
+          Call(Command::createInputSectionCmd(next(), false));
+      } else if (Tok == "KEEP") {
+        expect("(");
+        expect("*");
+        expect("(");
+        while (!Error && !skip(")"))
+          Call(Command::createInputSectionCmd(next(), true));
+        expect(")");
+      } else {
+        setError("unknown command " + Tok);
+      }
+    }
+
+    if (Error)
+      return;
+
+    StringRef Tok = peek();
+    std::vector<uint8_t> Filler;
+    if (Tok.startswith("=")) {
+      if (!Tok.startswith("=0x")) {
+        setError("filler should be a hexadecimal value");
+        return;
+      }
+      Tok = Tok.substr(3);
+      Filler = parseHex(Tok);
+      next();
+      Call(Command::createFillerCmd(Filler));
+    }
+  }
+};
+
 template <class ELFT>
-void LinkerScript<ELFT>::assignAddresses(
-    ArrayRef<OutputSectionBase<ELFT> *> Sections) {
+static void addSection(OutputSectionFactory<ELFT> &Factory,
+                       StringRef OutSecName, InputSectionBase<ELFT> *InSec,
+                       std::vector<OutputSectionBase<ELFT> *> &List) {
+  if (OutSecName == "/DISCARD/" || !InSec->Live)
+    return;
+
+  OutputSectionBase<ELFT> *OutSection = nullptr;
+  bool IsNew;
+  std::tie(OutSection, IsNew) = Factory.create(InSec, OutSecName);
+  OutSection->addSection(InSec);
+  if (IsNew)
+    List.push_back(OutSection);
+}
+
+template <class ELFT>
+std::vector<OutputSectionBase<ELFT> *>
+LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory,
+                                   SymbolTable<ELFT> &Symtab) {
+  // Create a list of input sections that were not assigned to output yet.
+  std::vector<InputSectionBase<ELFT> *> Unassigned;
+  for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
+       Symtab.getObjectFiles()) {
+    for (InputSectionBase<ELFT> *C : F->getSections())
+      if (!isDiscarded(C))
+        Unassigned.push_back(C);
+  }
+
+  std::vector<OutputSectionBase<ELFT> *> Sections;
+  StringRef OutSecName;
+  OutputSectionBase<ELFT> *OutSection = nullptr;
+  LayoutParser().run([&](const Command &Cmd) {
+    if (Cmd.Kind == OutSectionKind) {
+      OutSecName = Cmd.Name;
+      return;
+    }
+    if (OutSection && Cmd.Kind == FillerKind) {
+      OutSection->Filler = Cmd.Filler;
+      return;
+    }
+
+    if (Cmd.Kind != InputSectionKind)
+      return;
+
+    auto I = std::find_if(Unassigned.begin(), Unassigned.end(),
+                          [&](InputSectionBase<ELFT> *S) {
+                            return matchStr(Cmd.Pattern, S->getSectionName());
+                          });
+    if (I == Unassigned.end())
+      return;
+
+    InputSectionBase<ELFT> *InSec = *I;
+    Unassigned.erase(I);
+    addSection(Factory, OutSecName, InSec, 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) {
-    StringRef Name = Sec->getName();
-    if (getSectionIndex(Name) == INT_MAX)
-      Opt.Commands.push_back({SectionKind, {}, Name});
-  }
+  for (InputSectionBase<ELFT> *U : Unassigned)
+    addSection(Factory, getOutputSectionName(U), U, 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 ThreadBssOffset = 0;
 
-  for (SectionsCommand &Cmd : Opt.Commands) {
-    if (Cmd.Kind == ExprKind) {
-      Dot = evalExpr(Cmd.Expr, Dot);
-      continue;
-    }
-
-    OutputSectionBase<ELFT> *Sec = findSection<ELFT>(Sections, Cmd.SectionName);
+  DenseSet<OutputSectionBase<ELFT> *> Assigned;
+  auto Assign = [&](StringRef Name) {
+    OutputSectionBase<ELFT> *Sec = findSection<ELFT>(Sections, Name);
     if (!Sec)
-      continue;
+      return;
 
     if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
       uintX_t TVA = Dot + ThreadBssOffset;
       TVA = alignTo(TVA, Sec->getAlign());
       Sec->setVA(TVA);
       ThreadBssOffset = TVA - Dot + Sec->getSize();
-      continue;
+      Assigned.insert(Sec);
+      return;
     }
 
     if (Sec->getFlags() & SHF_ALLOC) {
       Dot = alignTo(Dot, Sec->getAlign());
       Sec->setVA(Dot);
       Dot += Sec->getSize();
-      continue;
+      Assigned.insert(Sec);
+      return;
     }
-  }
-}
-
-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) {
-  auto Begin = Opt.Commands.begin();
-  auto End = Opt.Commands.end();
-  auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
-    return N.Kind == SectionKind && N.SectionName == Name;
+  LayoutParser().run([&](const Command &Cmd) {
+    if (Cmd.Kind == ExprKind) {
+      Dot = evalExpr(Cmd.Expr, Dot);
+      return;
+    }
+    if (Cmd.Kind != OutSectionKind)
+      return;
+    Assign(Cmd.Name);
   });
-  return I == End ? INT_MAX : (I - Begin);
+
+  // Finally process all orphan sections.
+  for (OutputSectionBase<ELFT> *Sec : Sections)
+    if (!Assigned.count(Sec)) {
+      Assigned.insert(Sec);
+      Assign(Sec->getName());
+    }
 }
 
-// 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);
-  if (I == INT_MAX && J == INT_MAX)
-    return 0;
-  return I < J ? -1 : 1;
+void LinkerScript<ELFT>::checkLive(
+    std::vector<InputSectionBase<ELFT> *> &Sec,
+    std::function<void(InputSectionBase<ELFT> *)> MarkFn) {
+  LayoutParser().run([&](const Command &Cmd) {
+    if (Cmd.Kind != InputSectionKind)
+      return;
+    if (!Cmd.Keep)
+      return;
+    for (InputSectionBase<ELFT> *S : Sec)
+      if (matchStr(Cmd.Pattern, S->getSectionName()))
+        MarkFn(S);
+  });
 }
 
 // Returns true if S matches T. S can contain glob meta-characters.
@@ -338,10 +478,7 @@
   void readOutputArch();
   void readOutputFormat();
   void readSearchDir();
-  void readSections();
-
-  void readLocationCounterValue();
-  void readOutputSectionDescription();
+  void skipSections();
 
   const static StringMap<Handler> Cmd;
   ScriptConfiguration &Opt = *ScriptConfig;
@@ -359,7 +496,7 @@
     {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
     {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
     {"SEARCH_DIR", &ScriptParser::readSearchDir},
-    {"SECTIONS", &ScriptParser::readSections},
+    {"SECTIONS", &ScriptParser::skipSections},
     {";", &ScriptParser::readNothing}};
 
 void ScriptParser::run() {
@@ -500,70 +637,12 @@
   expect(")");
 }
 
-void ScriptParser::readSections() {
+void ScriptParser::skipSections() {
   Opt.DoLayout = true;
-  expect("{");
-  while (!Error && !skip("}")) {
-    StringRef Tok = peek();
-    if (Tok == ".")
-      readLocationCounterValue();
-    else
-      readOutputSectionDescription();
-  }
-}
-
-void ScriptParser::readLocationCounterValue() {
-  expect(".");
-  expect("=");
-  Opt.Commands.push_back({ExprKind, {}, ""});
-  SectionsCommand &Cmd = Opt.Commands.back();
-  while (!Error) {
-    StringRef Tok = next();
-    if (Tok == ";")
-      break;
-    Cmd.Expr.push_back(Tok);
-  }
-  if (Cmd.Expr.empty())
-    error("error in location counter expression");
-}
-
-void ScriptParser::readOutputSectionDescription() {
-  StringRef OutSec = next();
-  Opt.Commands.push_back({SectionKind, {}, OutSec});
-  expect(":");
-  expect("{");
-
-  while (!Error && !skip("}")) {
-    StringRef Tok = next();
-    if (Tok == "*") {
-      expect("(");
-      while (!Error && !skip(")"))
-        Opt.Sections.emplace_back(OutSec, next());
-    } else if (Tok == "KEEP") {
-      expect("(");
-      expect("*");
-      expect("(");
-      while (!Error && !skip(")")) {
-        StringRef Sec = next();
-        Opt.Sections.emplace_back(OutSec, Sec);
-        Opt.KeptSections.push_back(Sec);
-      }
-      expect(")");
-    } else {
-      setError("unknown command " + Tok);
-    }
-  }
-
-  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.SectionsData = Input.drop_front(Tokens[Pos - 1].begin() - Input.begin());
+  // Do nothing, just update the Pos and also
+  // script validation check is performed during scan.
+  Pos += LayoutParser().run([](const Command &Arg) {});
 }
 
 static bool isUnderSysroot(StringRef Path) {
Index: ELF/MarkLive.cpp
===================================================================
--- ELF/MarkLive.cpp
+++ ELF/MarkLive.cpp
@@ -173,6 +173,7 @@
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
+  std::vector<InputSectionBase<ELFT> *> KeepCandidate;
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *Sec : F->getSections())
@@ -182,10 +183,17 @@
         // referred by .eh_frame here.
         if (auto *EH = dyn_cast_or_null<EHInputSection<ELFT>>(Sec))
           scanEhFrameSection<ELFT>(*EH);
-        if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
+        if (isReserved(Sec))
           Enqueue({Sec, 0});
+        else if (ScriptConfig->DoLayout)
+          KeepCandidate.push_back(Sec);
       }
 
+  if (!KeepCandidate.empty())
+    Script<ELFT>::X->checkLive(KeepCandidate, [&](InputSectionBase<ELFT> *K) {
+      Enqueue({K, 0});
+    });
+
   // Mark all reachable sections.
   while (!Q.empty())
     forEachSuccessor<ELFT>(Q.pop_back_val(), Enqueue);
Index: ELF/OutputSections.h
===================================================================
--- ELF/OutputSections.h
+++ ELF/OutputSections.h
@@ -13,6 +13,7 @@
 #include "Config.h"
 
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Object/ELF.h"
@@ -97,6 +98,8 @@
   virtual void writeTo(uint8_t *Buf) {}
   virtual ~OutputSectionBase() = default;
 
+  std::vector<uint8_t> Filler;
+
 protected:
   StringRef Name;
   Elf_Shdr Header;
@@ -614,6 +617,38 @@
   static OutputSectionBase<ELFT> *ProgramHeaders;
 };
 
+// This class knows how to create an output section for a given
+// input section. Output section type is determined by various
+// factors, including input section's sh_flags, sh_type and
+// linker scripts.
+template <bool Is64Bits> struct SectionKey {
+  typedef typename std::conditional<Is64Bits, uint64_t, uint32_t>::type uintX_t;
+  StringRef Name;
+  uint32_t Type;
+  uintX_t Flags;
+  uintX_t Alignment;
+};
+
+template <class ELFT> class OutputSectionFactory {
+  typedef typename ELFT::Shdr Elf_Shdr;
+  typedef typename ELFT::uint uintX_t;
+  typedef typename 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) {
+    return Map.lookup({Name, Type, Flags, 0});
+  }
+
+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;
@@ -643,4 +678,25 @@
 } // 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() {
+    return Key{DenseMapInfo<StringRef>::getEmptyKey(), 0, 0, 0};
+  }
+  static Key getTombstoneKey() {
+    return Key{DenseMapInfo<StringRef>::getTombstoneKey(), 0, 0, 0};
+  }
+  static unsigned getHashValue(const Key &Val) {
+    return hash_combine(Val.Name, Val.Type, Val.Flags, Val.Alignment);
+  }
+  static bool isEqual(const Key &LHS, const Key &RHS) {
+    return DenseMapInfo<StringRef>::isEqual(LHS.Name, RHS.Name) &&
+           LHS.Type == RHS.Type && LHS.Flags == RHS.Flags &&
+           LHS.Alignment == RHS.Alignment;
+  }
+};
+} // namespace llvm
+
 #endif // LLD_ELF_OUTPUT_SECTIONS_H
Index: ELF/OutputSections.cpp
===================================================================
--- ELF/OutputSections.cpp
+++ ELF/OutputSections.cpp
@@ -934,7 +934,6 @@
 }
 
 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 (Config->Threads) {
@@ -1692,6 +1691,61 @@
 }
 
 template <class ELFT>
+std::pair<OutputSectionBase<ELFT> *, bool>
+OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
+                                   StringRef OutsecName) {
+  SectionKey<ELFT::Is64Bits> Key = createKey(C, OutsecName);
+  OutputSectionBase<ELFT> *&Sec = Map[Key];
+  if (Sec)
+    return {Sec, false};
+
+  switch (C->SectionKind) {
+  case InputSectionBase<ELFT>::Regular:
+    Sec = new OutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
+    break;
+  case InputSectionBase<ELFT>::EHFrame:
+    Sec = new EHOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
+    break;
+  case InputSectionBase<ELFT>::Merge:
+    Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags,
+                                       Key.Alignment);
+    break;
+  case InputSectionBase<ELFT>::MipsReginfo:
+    Sec = new MipsReginfoOutputSection<ELFT>();
+    break;
+  case InputSectionBase<ELFT>::MipsOptions:
+    Sec = new MipsOptionsOutputSection<ELFT>();
+    break;
+  }
+  return {Sec, true};
+}
+
+template <class ELFT>
+SectionKey<ELFT::Is64Bits>
+OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,
+                                      StringRef OutsecName) {
+  const Elf_Shdr *H = C->getSectionHdr();
+  uintX_t Flags = H->sh_flags & ~SHF_GROUP;
+
+  // For SHF_MERGE we create different output sections for each alignment.
+  // This makes each output section simple and keeps a single level mapping from
+  // input to output.
+  uintX_t Alignment = 0;
+  if (isa<MergeInputSection<ELFT>>(C))
+    Alignment = std::max(H->sh_addralign, H->sh_entsize);
+
+  // GNU as can give .eh_frame section type SHT_PROGBITS or SHT_X86_64_UNWIND
+  // depending on the construct. We want to canonicalize it so that
+  // there is only one .eh_frame in the end.
+  uint32_t Type = H->sh_type;
+  if (Type == SHT_PROGBITS && Config->EMachine == EM_X86_64 &&
+      isa<EHInputSection<ELFT>>(C))
+    Type = SHT_X86_64_UNWIND;
+
+  return SectionKey<ELFT::Is64Bits>{OutsecName, Type, Flags, Alignment};
+}
+
+template <class ELFT>
 MipsOptionsOutputSection<ELFT>::MipsOptionsOutputSection()
     : OutputSectionBase<ELFT>(".MIPS.options", SHT_MIPS_OPTIONS,
                               SHF_ALLOC | SHF_MIPS_NOSTRIP) {
@@ -1835,5 +1889,10 @@
 template class BuildIdSha1<ELF32BE>;
 template class BuildIdSha1<ELF64LE>;
 template class BuildIdSha1<ELF64BE>;
+
+template class OutputSectionFactory<ELF32LE>;
+template class OutputSectionFactory<ELF32BE>;
+template class OutputSectionFactory<ELF64LE>;
+template class OutputSectionFactory<ELF64BE>;
 }
 }
Index: ELF/Writer.h
===================================================================
--- ELF/Writer.h
+++ ELF/Writer.h
@@ -10,14 +10,29 @@
 #ifndef LLD_ELF_WRITER_H
 #define LLD_ELF_WRITER_H
 
+namespace llvm {
+class StringRef;
+}
+
 namespace lld {
 namespace elf {
 
 template <class ELFT> class SymbolTable;
+template <class ELFT> class InputSectionBase;
+template <class ELFT> class ObjectFile;
 
 template <class ELFT> void writeResult(SymbolTable<ELFT> *Symtab);
 
 template <class ELFT> void markLive();
+
+template <class ELFT>
+llvm::StringRef getOutputSectionName(InputSectionBase<ELFT> *S);
+
+template <class ELFT> bool isDiscarded(InputSectionBase<ELFT> *IS);
+
+template <class ELFT>
+void reportDiscarded(InputSectionBase<ELFT> *IS,
+                     const elf::ObjectFile<ELFT> &File);
 }
 }
 
Index: ELF/Writer.cpp
===================================================================
--- ELF/Writer.cpp
+++ ELF/Writer.cpp
@@ -10,6 +10,7 @@
 #include "Writer.h"
 #include "Config.h"
 #include "LinkerScript.h"
+#include "InputSection.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Target.h"
@@ -60,7 +61,11 @@
 
   void copyLocalSymbols();
   void addReservedSymbols();
+
+  std::vector<OutputSectionBase<ELFT> *>
+  createRegularSections(OutputSectionFactory<ELFT> &Factory);
   void createSections();
+
   void addPredefinedSections();
   bool needsGot();
 
@@ -81,8 +86,6 @@
   void writeHeader();
   void writeSections();
   void writeBuildId();
-  bool isDiscarded(InputSectionBase<ELFT> *IS) const;
-  StringRef getOutputSectionName(InputSectionBase<ELFT> *S) const;
   bool needsInterpSection() const {
     return !Symtab.getSharedFiles().empty() && !Config->DynamicLinker.empty();
   }
@@ -119,6 +122,30 @@
 };
 } // anonymous namespace
 
+template <class ELFT>
+StringRef elf::getOutputSectionName(InputSectionBase<ELFT> *S) {
+  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> bool elf::isDiscarded(InputSectionBase<ELFT> *S) {
+  return !S || S == &InputSection<ELFT>::Discarded || !S->Live;
+}
+
+template <class ELFT>
+void elf::reportDiscarded(InputSectionBase<ELFT> *IS,
+                          const elf::ObjectFile<ELFT> &File) {
+  if (!Config->PrintGcSections || !IS || IS->Live)
+    return;
+  llvm::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;
@@ -247,37 +274,6 @@
   check(Buffer->commit());
 }
 
-namespace {
-template <bool Is64Bits> struct SectionKey {
-  typedef typename std::conditional<Is64Bits, uint64_t, uint32_t>::type uintX_t;
-  StringRef Name;
-  uint32_t Type;
-  uintX_t Flags;
-  uintX_t Alignment;
-};
-}
-namespace llvm {
-template <bool Is64Bits> struct DenseMapInfo<SectionKey<Is64Bits>> {
-  static SectionKey<Is64Bits> getEmptyKey() {
-    return SectionKey<Is64Bits>{DenseMapInfo<StringRef>::getEmptyKey(), 0, 0,
-                                0};
-  }
-  static SectionKey<Is64Bits> getTombstoneKey() {
-    return SectionKey<Is64Bits>{DenseMapInfo<StringRef>::getTombstoneKey(), 0,
-                                0, 0};
-  }
-  static unsigned getHashValue(const SectionKey<Is64Bits> &Val) {
-    return hash_combine(Val.Name, Val.Type, Val.Flags, Val.Alignment);
-  }
-  static bool isEqual(const SectionKey<Is64Bits> &LHS,
-                      const SectionKey<Is64Bits> &RHS) {
-    return DenseMapInfo<StringRef>::isEqual(LHS.Name, RHS.Name) &&
-           LHS.Type == RHS.Type && LHS.Flags == RHS.Flags &&
-           LHS.Alignment == RHS.Alignment;
-  }
-};
-}
-
 // Returns the number of relocations processed.
 template <class ELFT>
 static unsigned handleTlsRelocation(uint32_t Type, SymbolBody &Body,
@@ -905,10 +901,6 @@
                             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();
 
@@ -1049,36 +1041,6 @@
 }
 
 template <class ELFT>
-StringRef Writer<ELFT>::getOutputSectionName(InputSectionBase<ELFT> *S) const {
-  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 reportDiscarded(InputSectionBase<ELFT> *IS,
-                     const std::unique_ptr<elf::ObjectFile<ELFT>> &File) {
-  if (!Config->PrintGcSections || !IS || IS->Live)
-    return;
-  llvm::errs() << "removing unused section from '" << IS->getSectionName()
-               << "' in file '" << File->getName() << "'\n";
-}
-
-template <class ELFT>
-bool Writer<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) const {
-  return !S || S == &InputSection<ELFT>::Discarded || !S->Live ||
-         Script<ELFT>::X->isDiscarded(S);
-}
-
-template <class ELFT>
 static Symbol *addOptionalSynthetic(SymbolTable<ELFT> &Table, StringRef Name,
                                     OutputSectionBase<ELFT> *Sec,
                                     typename ELFT::uint Val) {
@@ -1116,87 +1078,6 @@
   return true;
 }
 
-// This class knows how to create an output section for a given
-// input section. Output section type is determined by various
-// factors, including input section's sh_flags, sh_type and
-// linker scripts.
-namespace {
-template <class ELFT> class OutputSectionFactory {
-  typedef typename ELFT::Shdr Elf_Shdr;
-  typedef typename ELFT::uint uintX_t;
-
-public:
-  std::pair<OutputSectionBase<ELFT> *, bool> create(InputSectionBase<ELFT> *C,
-                                                    StringRef OutsecName);
-
-  OutputSectionBase<ELFT> *lookup(StringRef Name, uint32_t Type,
-                                  uintX_t Flags) {
-    return Map.lookup({Name, Type, Flags, 0});
-  }
-
-private:
-  SectionKey<ELFT::Is64Bits> createKey(InputSectionBase<ELFT> *C,
-                                       StringRef OutsecName);
-
-  SmallDenseMap<SectionKey<ELFT::Is64Bits>, OutputSectionBase<ELFT> *> Map;
-};
-}
-
-template <class ELFT>
-std::pair<OutputSectionBase<ELFT> *, bool>
-OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
-                                   StringRef OutsecName) {
-  SectionKey<ELFT::Is64Bits> Key = createKey(C, OutsecName);
-  OutputSectionBase<ELFT> *&Sec = Map[Key];
-  if (Sec)
-    return {Sec, false};
-
-  switch (C->SectionKind) {
-  case InputSectionBase<ELFT>::Regular:
-    Sec = new OutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
-    break;
-  case InputSectionBase<ELFT>::EHFrame:
-    Sec = new EHOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
-    break;
-  case InputSectionBase<ELFT>::Merge:
-    Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags,
-                                       Key.Alignment);
-    break;
-  case InputSectionBase<ELFT>::MipsReginfo:
-    Sec = new MipsReginfoOutputSection<ELFT>();
-    break;
-  case InputSectionBase<ELFT>::MipsOptions:
-    Sec = new MipsOptionsOutputSection<ELFT>();
-    break;
-  }
-  return {Sec, true};
-}
-
-template <class ELFT>
-SectionKey<ELFT::Is64Bits>
-OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,
-                                      StringRef OutsecName) {
-  const Elf_Shdr *H = C->getSectionHdr();
-  uintX_t Flags = H->sh_flags & ~SHF_GROUP;
-
-  // For SHF_MERGE we create different output sections for each alignment.
-  // This makes each output section simple and keeps a single level mapping from
-  // input to output.
-  uintX_t Alignment = 0;
-  if (isa<MergeInputSection<ELFT>>(C))
-    Alignment = std::max(H->sh_addralign, H->sh_entsize);
-
-  // GNU as can give .eh_frame section type SHT_PROGBITS or SHT_X86_64_UNWIND
-  // depending on the construct. We want to canonicalize it so that
-  // there is only one .eh_frame in the end.
-  uint32_t Type = H->sh_type;
-  if (Type == SHT_PROGBITS && Config->EMachine == EM_X86_64 &&
-      isa<EHInputSection<ELFT>>(C))
-    Type = SHT_X86_64_UNWIND;
-
-  return SectionKey<ELFT::Is64Bits>{OutsecName, Type, Flags, Alignment};
-}
-
 // The linker is expected to define some symbols depending on
 // the linking result. This function defines such symbols.
 template <class ELFT> void Writer<ELFT>::addReservedSymbols() {
@@ -1275,40 +1156,42 @@
     reinterpret_cast<OutputSection<ELFT> *>(S)->sortCtorsDtors();
 }
 
-// Create output section objects and add them to OutputSections.
-template <class ELFT> void Writer<ELFT>::createSections() {
-  // Add .interp first because some loaders want to see that section
-  // on the first page of the executable file when loaded into memory.
-  if (needsInterpSection())
-    OutputSections.push_back(Out<ELFT>::Interp);
-
-  // A core file does not usually contain unmodified segments except
-  // the first page of the executable. Add the build ID section now
-  // so that the section is included in the first page.
-  if (Out<ELFT>::BuildId)
-    OutputSections.push_back(Out<ELFT>::BuildId);
+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);
+        reportDiscarded(C, *F.get());
         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);
+  }
 
   Out<ELFT>::Bss = static_cast<OutputSection<ELFT> *>(
       Factory.lookup(".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE));
@@ -1414,8 +1297,9 @@
   // This function adds linker-created Out<ELFT>::* sections.
   addPredefinedSections();
 
-  std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                   compareSections<ELFT>);
+  if (!ScriptConfig->DoLayout)
+    std::stable_sort(OutputSections.begin(), OutputSections.end(),
+                     compareSections<ELFT>);
 
   unsigned I = 1;
   for (OutputSectionBase<ELFT> *Sec : OutputSections) {
@@ -1462,6 +1346,18 @@
       OutputSections.push_back(C);
   };
 
+  // Add .interp at first because some loaders want to see that section
+  // on the first page of the executable file when loaded into memory.
+  auto I = OutputSections.begin();
+  if (needsInterpSection())
+    I = OutputSections.insert(I, Out<ELFT>::Interp);
+
+  // A core file does not usually contain unmodified segments except
+  // the first page of the executable. Add the build ID section now
+  // so that the section is included in the first page.
+  if (Out<ELFT>::BuildId)
+    OutputSections.insert(I, Out<ELFT>::BuildId);
+
   // This order is not the same as the final output order
   // because we sort the sections using their attributes below.
   Add(Out<ELFT>::SymTab);