[ELF2] SECTIONS command basic support

[denis-protivensky]

Summary

Add support of SECTIONS command:

• determine output section by input section name
• discard input sections
• order output sections accordingly
• don't add bounding symbols (__start/__stop) for sections defined in the linker script

[grimar]

ELF/Writer.cpp

453 ↗

(On Diff #38634)

This could be in class declaration.

495 ↗

(On Diff #38634)

Does not seem that llvm_unreachable is really needed. Code just few lines above creates OutputSections or MergeOutputSections, no any other choices.

885 ↗

(On Diff #38634)

This would work a bit faster in some cases:

if (Config->OutputSections.find(A->getName()) == ItEnd ||
Config->OutputSections.find(B->getName()) == ItEnd )
{...

[denis-protivensky]

ELF/Writer.cpp

453 ↗

(On Diff #38634)

Ok.

495 ↗

(On Diff #38634)

There are other choices coming from the cached values of Map. It now holds only Bss before the loop, but who knows what can be added later. That's a good form of protection.

885 ↗

(On Diff #38634)

I don't think we should sacrifice readability since performance benefit is not clear here.
I need iterators after this check, and I don't want to write C-style code like:

if ((ItA = Config->.... ) == ItEnd ||
  ((ItB = Config->.... ) == ItEnd))

I will moreover need to define full iterator types before usage instead of auto deduction.

[grimar]

ELF/Writer.cpp

885 ↗

(On Diff #38634)

I didnt notice at first that you use ItA/ItB after that. Ok then.

[denis-protivensky]

ELF/Writer.cpp

885 ↗

(On Diff #38634)

I actually can break it up into two separate checks so it'll be more optimal and won't affect code style.

[grimar]

ELF/Writer.cpp

885 ↗

(On Diff #38634)

I thought about that but for me it will look not very readable. Not sure if that possible little speed up worth that.

[ruiu]

ELF/OutputSections.h

98–99 ↗

(On Diff #38634)

Why do you need this?

ELF/Writer.cpp

92–107 ↗

(On Diff #38634)

No, please don't make another Writer class. This is over-engineering. There's no such need to support two writers, one for ELF without linker script and another for ELF + linker script.

[denis-protivensky]

Updated:

• Remove dynamic casting of output section classes
• Remove separate class for linker script support
• Move linker script-related code to Writer and use conditional checks where needed

[grimar]

ELF/Config.h

38 ↗

(On Diff #38716)

May be regroup would look better ?

llvm::StringRef InputFile;
std::vector<llvm::StringRef> Names;
std::vector<llvm::StringRef> ExcludeFiles;

ELF/Writer.cpp

460 ↗

(On Diff #38716)

What about next one ?

 if (!IS || !IS->isLive() || IS == &InputSection<ELFT>::Discarded)
    return true;

return hasCustomSections() && InputToOutputSection.lookup(IS->getSectionName()) == "/DISCARD/";

910 ↗

(On Diff #38716)

I think you want to use & after autos:
auto &OutSec, auto &InSec ...

[denis-protivensky]

ELF/Config.h

38 ↗

(On Diff #38716)

Ok, maybe.

ELF/Writer.cpp

460 ↗

(On Diff #38716)

A matter of taste again. Okay.

910 ↗

(On Diff #38716)

Yes, that's right.

[denis-protivensky]

Update:

• Style fixes
• Use reference in range-for-loop (auto &)

[ruiu]

ELF/LinkerScript.cpp

250 ↗

(On Diff #38723)

I wouldn't write this in this functional style. This can be written in a plain C style if you define skip(S) which returns true if the next token is S.

expect("(");
while (!skip(")") {
  StringRef Tok = next();
  if (Tok == "EXCLUDE_FILE") {
  ...

ELF/Writer.cpp

461–465 ↗

(On Diff #38723)

Why don't you create start/stop symbols if the section is defined using a linker script? Is that a documented behavior?

614 ↗

(On Diff #38723)

I don't like to add more code to createSections() which is already too long. Move this lambda out of this function.

[grimar]

ELF/Writer.cpp

909 ↗

(On Diff #38723)

I think you can do the same for auto Name.

[denis-protivensky]

ELF/LinkerScript.cpp

250 ↗

(On Diff #38723)

mapBraces actually does the same. I can change peek to skip, but why to produce code duplication where it can be avoided? Procedural style may be more cumbersome here than the current functional implementation.

ELF/Writer.cpp

461–465 ↗

(On Diff #38723)

If one defines output section description, they may define all needed symbols manually.
That's why I think any default actions that can be achieved with linker script should be suppressed.

614 ↗

(On Diff #38723)

I need RegularSections, which is local to the method. It's captured in the lambda, and I think it would be ugly to pass it to the comparison function along with two output sections to compare. Any ideas how to make it better?

909 ↗

(On Diff #38723)

I'll use real types instead.

[ruiu]

ELF/LinkerScript.cpp

250 ↗

(On Diff #38723)

By duplicate, do you mean this part? I don't think this is duplicate.

expect("(");
while (!skip(")") {

ELF/Writer.cpp

614 ↗

(On Diff #38723)

Why do you need RegularSections in the first place? What is this !RegularSections.(A)||!RegularSections.count(B) condition for?

[denis-protivensky]

ELF/Writer.cpp

614 ↗

(On Diff #38723)

The intent is to sort 'specific' sections like .symtab, .strtab and others with default sorting order even if some of these names are defined in linker script. Can't figure out why the tests pass without this check as I thought I specifically checked that case. Will look at this more.

[ruiu]

2015/10/29 8:31 "Denis Protivensky" <[e-mail]>:

denis-protivensky added inline comments.

Comment at: ELF/Writer.cpp:614
@@ -574,3 +613,3 @@

• std::stable_sort(OutputSections.begin(), OutputSections.end(),
• compareOutputSections<ELFT>);

+ std::stable_sort(

+ OutputSections.begin(), OutputSections.end(),

ruiu wrote:

denis-protivensky wrote:

ruiu wrote:

I don't like to add more code to createSections() which is already

too long. Move this lambda out of this function.

I need RegularSections, which is local to the method. It's captured

in the lambda, and I think it would be ugly to pass it to the comparison
function along with two output sections to compare. Any ideas how to make
it better?

Why do you need RegularSections in the first place? What is this

!RegularSections.(A)||!RegularSections.count(B) condition for?

The intent is to sort 'specific' sections like .symtab, .strtab and

others with default sorting order even if some of these names are defined
in linker script. Can't figure out why the tests pass without this check as
I thought I specifically checked that case. Will look at this more.

I don't think we need that protection. If users try to reorder such
sections, we should do that as instructed, no?

http://reviews.llvm.org/D14140

[denis-protivensky]

I don't think we need that protection. If users try to reorder such
sections, we should do that as instructed, no?

First of all, I reproduced the case when defining 'specific' section in the SECTIONS command affects its ordering in the resulting file without the check, so this check works as I expected.

Concerning ordering of 'specific' sections:
The goal of the SECTIONS command is to layout sections from input files to the corresponding output sections. 'Specific' sections as .got, .plt, .interp and most others don't have input sections at all and are generated by the linker logic. This means that we cannot affect the contents of such sections, and the output section description command of format

.interp : { *(.interp) }

is void because there are no input .interp sections, and such empty output sections are discarded by linker rules. The only way this format of command worked is to define custom .interp section (possibly of SHT_PROGBITS/_NOBITS type). Then it will be considered during layout, but that's a specific case and it's checked in tests (with .shstrtab custom section).
I conclude that output section descriptions affect only PROGBITS/NOBITS section types, which are represented as OutputSection/MergeOutputSection in lld, and we currently create only these sections from output section descriptions.
That's why I think the ordering should also affect only these sections, which are stored in RegularSections map in code.

Just as a note: ld doesn't seem as well to reorder 'specific' sections even if defined in linker script.

[denis-protivensky]

ELF/LinkerScript.cpp

250 ↗

(On Diff #38723)

Do you think this code:

expect("(");
while (!skip(")")) {
  StringRef Tok = next();
  if (Tok == "EXCLUDE_FILE") {
    expect("(");
    while (!skip(")"))
      InSec.ExcludeFiles.push_back(next());
  } else
    InSec.Names.push_back(Tok);
}

is simpler and more clear than the original one:

mapBraces("(", ")", [this, &InSec]() {
  StringRef Tok = next();
  if (Tok == "EXCLUDE_FILE")
    mapBraces("(", ")",
              [this, &InSec]() { InSec.ExcludeFiles.push_back(next()); });
  else
    InSec.Names.push_back(Tok);
});

?

[ruiu]

I think this falls in the category of undefined behaviors if there was a
spec of the linker script. Since there's no standard or specification for
the linker script, we need to do something that we think reasonable. A
pitfall we want to avoid is to copy every detail of the GNU linker. So can
you please minimize the impact of the patch to the regular flow? I'd
restore code for start/stop symbols and for RegularSections, and
reorder "non-regular" sections if instructed to do so.

[ruiu]

ELF/LinkerScript.cpp

250 ↗

(On Diff #38723)

Yes, I do think so (as a C/C++ programmer and as a Scheme programmer). The former is much more straightforward C++ and easier to understand than the latter, especially for people who are not very familiar with all the code in this file.

[denis-protivensky]

Updated:

• Replace mapBraces method with procedural checks in the linker script parser
• Change peek() -> skip() in the parser
• Remove custom bounding symbols processing for linker script
• Remove checks for regular section ordering for linker script
• Change section comparison lambda with method
• Remove not used fields of input section description struct

[ruiu]

ELF/Config.h

33–35 ↗

(On Diff #38891)

A struct with one field doesn't have much value. Please remove.

ELF/LinkerScript.cpp

50–54 ↗

(On Diff #38891)

Move readInputSectionDescription and readOutputSectionDescription at the end of this list (after one blank line) so that helper functions are not mixed with readers for top-level constructs.

152–153 ↗

(On Diff #38891)

Remove this blank line and a comment. (If you really want to add a comment to this short function, write that as a function comment, but I think we don't need that.)

245–247 ↗

(On Diff #38891)

You can remove {}.

ELF/Writer.cpp

435 ↗

(On Diff #38891)

Do you really need to check for that? If it's empty, find() will not find anything, so this check seems extraneous.

453 ↗

(On Diff #38891)

Rename discardInputSection -> isDiscarded

456 ↗

(On Diff #38891)

Is this check needed?

463 ↗

(On Diff #38891)

Is this needed?

622–626 ↗

(On Diff #38891)

This may be able to be written as

std::stable_sort(OutputSections.begin(), OutputSections.end(), compareSections);

[denis-protivensky]

Updated:

• Style fixes in linker script
• Remove InputSectionDescription
• Remove hasCustomSections check
• Rename discardInputSection -> isDiscarded
• Make compareSections static

[ruiu]

ELF/Writer.cpp

550–557 ↗

(On Diff #39034)

for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab.getObjectFiles())
  for (InputSectionBase<ELFT> *C : F->getSections())
    if (!isDiscarded(C))
      if (auto *S = dyn_cast<InputSection<ELFT>>(C))
        scanRelocs(*S);

906–911 ↗

(On Diff #39034)

Looks like OutputSectionDescription doesn't have to be a struct. We can make Config->OutputSections of type StringMap<StringRef> which maps input section names to output section names.

[• rafael]

First of all, I reproduced the case when defining 'specific' section in the SECTIONS command affects its ordering in the resulting file without the check, so this check works as I expected.

Concerning ordering of 'specific' sections:
The goal of the SECTIONS command is to layout sections from input files to the corresponding output sections. 'Specific' sections as .got, .plt, .interp and most others don't have input sections at all and are generated by the linker logic. This means that we cannot affect the contents of such sections, and the output section description command of format

.interp : { *(.interp) }

is void because there are no input .interp sections, and such empty output sections are discarded by linker rules. The only way this format of command worked is to define custom .interp section (possibly of SHT_PROGBITS/_NOBITS type). Then it will be considered during layout, but that's a specific case and it's checked in tests (with .shstrtab custom section).
I conclude that output section descriptions affect only PROGBITS/NOBITS section types, which are represented as OutputSection/MergeOutputSection in lld, and we currently create only these sections from output section descriptions.
That's why I think the ordering should also affect only these sections, which are stored in RegularSections map in code.

Just as a note: ld doesn't seem as well to reorder 'specific' sections even if defined in linker script.

It is not clear if this is needed by real program. For now just leave
it out to have a simpler code. Even if it is needed, it would be
better to just organize the code as

• add sections from input files
• sort
• add linker generated sections
• sort the end + merge

no?
Cheers,
Rafael

[denis-protivensky]

In D14140#282350, @rafael wrote:

It is not clear if this is needed by real program. For now just leave
it out to have a simpler code. Even if it is needed, it would be
better to just organize the code as

• add sections from input files
• sort
• add linker generated sections
• sort the end + merge

no?

I'll leave simpler code, thanks.

ELF/Writer.cpp

550–557 ↗

(On Diff #39034)

Ok.

906–911 ↗

(On Diff #39034)

I can't substitute MapVector with StringMap since I need to know original ordering of output sections defined in linker script so I can sort them accordingly.
I'll remove the OutputSectionDescription structure and use MapVector<StringRef, std::vector<StringRef>> instead.

[denis-protivensky]

Updated:

• Remove OutputSectionDescription structure
• Simplify checks in scan relocs loop

[ruiu]

One question is the performance with this patch. Does this slow down the linker? If so, how much?

ELF/Writer.cpp

935 ↗

(On Diff #39689)

Can you avoid using a word "parse" here? Linker scripts are and should be parsed by LinkerScript.cpp, so every time I see this name, it feels like a domain error. I don't have a good suggestion, but I'd probably name createSectionMap or something.

[denis-protivensky]

Updated:

• Rename parseSectionDescriptions -> buildSectionMap

[denis-protivensky]

In D14140#285339, @ruiu wrote:

One question is the performance with this patch. Does this slow down the linker? If so, how much?

The average of 20 iterations of self-linking lld on my machine:

• without the patch = 420 ms
• with the patch = 425 ms

[ruiu]

LGTM with a nit.

ELF/Writer.cpp

40 ↗

(On Diff #39902)

Please move this to the beginning of Writer<ELFT>::run().

lld/trunk/ELF/Config.h

 //===- Config.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_CONFIG_H
 #define LLD_ELF_CONFIG_H
 
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ELF.h"
 
 #include <vector>
 
 namespace lld {
 namespace elf2 {
 
struct Configuration {
   llvm::StringRef Entry;
   llvm::StringRef Emulation;
   llvm::StringRef Fini;
   llvm::StringRef Init;
   llvm::StringRef OutputFile;
   llvm::StringRef SoName;
   llvm::StringRef Sysroot;
   std::string RPath;
+  llvm::MapVector<llvm::StringRef, std::vector<llvm::StringRef>> OutputSections;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> Undefined;
   bool AllowMultipleDefinition;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool DiscardAll;
   bool DiscardLocals;
   bool DiscardNone;

lld/trunk/ELF/LinkerScript.cpp

public:
   LinkerScript(BumpPtrAllocator *A, StringRef S)
       : Saver(*A), Tokens(tokenize(S)) {}
   void run();
 
 private:
   static std::vector<StringRef> tokenize(StringRef S);
   static StringRef skipSpace(StringRef S);
   StringRef next();
+  bool skip(StringRef Tok);
   bool atEOF() { return Tokens.size() == Pos; }
   void expect(StringRef Expect);
 
   void addFile(StringRef Path);
 
   void readAsNeeded();
   void readEntry();
   void readExtern();
   void readGroup();
   void readInclude();
   void readOutput();
   void readOutputArch();
   void readOutputFormat();
   void readSearchDir();
+  void readSections();
+
+  void readOutputSectionDescription();
 
   StringSaver Saver;
   std::vector<StringRef> Tokens;
   size_t Pos = 0;
 };
 }
 
 void LinkerScript::run() {
while (!atEOF()) {
     } else if (Tok == "OUTPUT") {
       readOutput();
     } else if (Tok == "OUTPUT_ARCH") {
       readOutputArch();
     } else if (Tok == "OUTPUT_FORMAT") {
       readOutputFormat();
     } else if (Tok == "SEARCH_DIR") {
       readSearchDir();
+    } else if (Tok == "SECTIONS") {
+      readSections();
     } else {
       error("unknown directive: " + Tok);
     }
   }
 }
 
 // Split S into linker script tokens.
 std::vector<StringRef> LinkerScript::tokenize(StringRef S) {
for (;;) {
     size_t Size = S.size();
     S = S.ltrim();
     if (S.size() == Size)
       return S;
   }
 }
 
 StringRef LinkerScript::next() {
-  if (Pos == Tokens.size())
+  if (atEOF())
     error("unexpected EOF");
   return Tokens[Pos++];
 }
 
+bool LinkerScript::skip(StringRef Tok) {
+  if (atEOF())
+    error("unexpected EOF");
+  if (Tok != Tokens[Pos])
+    return false;
+  ++Pos;
+  return true;
+}
+
 void LinkerScript::expect(StringRef Expect) {
   StringRef Tok = next();
   if (Tok != Expect)
     error(Expect + " expected, but got " + Tok);
 }
 
 void LinkerScript::addFile(StringRef S) {
   if (sys::path::is_absolute(S)) {

 }
 
 void LinkerScript::readSearchDir() {
   expect("(");
   Config->SearchPaths.push_back(next());
   expect(")");
 }
 
+void LinkerScript::readSections() {
+  expect("{");
+  while (!skip("}"))
+    readOutputSectionDescription();
+}
+
+void LinkerScript::readOutputSectionDescription() {
+  StringRef Name = next();
+  std::vector<StringRef> &InputSections = Config->OutputSections[Name];
+
+  expect(":");
+  expect("{");
+  while (!skip("}")) {
+    next(); // Skip input file name.
+    expect("(");
+    while (!skip(")"))
+      InputSections.push_back(next());
+  }
+}
+
 // Entry point. The other functions or classes are private to this file.
 void lld::elf2::readLinkerScript(BumpPtrAllocator *A, MemoryBufferRef MB) {
   LinkerScript(A, MB.getBuffer()).run();
 }

lld/trunk/ELF/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
 #include "Config.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Target.h"
 
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 
private:
   void copyLocalSymbols();
   void createSections();
   template <bool isRela>
   void scanRelocs(InputSectionBase<ELFT> &C,
                   iterator_range<const Elf_Rel_Impl<ELFT, isRela> *> Rels);
   void scanRelocs(InputSection<ELFT> &C);
   void scanRelocs(InputSectionBase<ELFT> &S, const Elf_Shdr &RelSec);
   void assignAddresses();
+  void buildSectionMap();
   void openFile(StringRef OutputPath);
   void writeHeader();
   void writeSections();
+  bool isDiscarded(InputSectionBase<ELFT> *IS) const;
+  StringRef getOutputSectionName(StringRef S) const;
   bool needsInterpSection() const {
     return !Symtab.getSharedFiles().empty() && !Config->DynamicLinker.empty();
   }
   bool isOutputDynamic() const {
     return !Symtab.getSharedFiles().empty() || Config->Shared;
   }
   uintX_t getEntryAddr() const;
   int getPhdrsNum() const;
void setPhdr(Elf_Phdr *PH, uint32_t Type, uint32_t Flags, uintX_t FileOff,
                uintX_t VA, uintX_t Size, uintX_t Align);
   void copyPhdr(Elf_Phdr *PH, OutputSectionBase<ELFT> *From);
 
   SymbolTable<ELFT> &Symtab;
   std::vector<Elf_Phdr> Phdrs;
 
   uintX_t FileSize;
   uintX_t SectionHeaderOff;
+
+  llvm::StringMap<llvm::StringRef> InputToOutputSection;
 };
 } // anonymous namespace
 
 template <class ELFT> void lld::elf2::writeResult(SymbolTable<ELFT> *Symtab) {
   // Initialize output sections that are handled by Writer specially.
   // Don't reorder because the order of initialization matters.
   InterpSection<ELFT> Interp;
   Out<ELFT>::Interp = &Interp;
template <class ELFT> void lld::elf2::writeResult(SymbolTable<ELFT> *Symtab) {
   DynamicSection<ELFT> Dynamic(*Symtab);
   Out<ELFT>::Dynamic = &Dynamic;
 
   Writer<ELFT>(*Symtab).run();
 }
 
 // The main function of the writer.
 template <class ELFT> void Writer<ELFT>::run() {
+  buildSectionMap();
   if (!Config->DiscardAll)
     copyLocalSymbols();
   createSections();
   assignAddresses();
   openFile(Config->OutputFile);
   writeHeader();
   writeSections();
   error(Buffer->commit());
for (SharedSymbol<ELFT> *C : Syms) {
     Out<ELFT>::Bss->updateAlign(Align);
     Off = RoundUpToAlignment(Off, Align);
     C->OffsetInBSS = Off;
     Off += Sym.st_size;
   }
   Out<ELFT>::Bss->setSize(Off);
 }
 
-static StringRef getOutputName(StringRef S) {
+template <class ELFT>
+StringRef Writer<ELFT>::getOutputSectionName(StringRef S) const {
+  auto It = InputToOutputSection.find(S);
+  if (It != std::end(InputToOutputSection))
+    return It->second;
+
   if (S.startswith(".text."))
     return ".text";
   if (S.startswith(".rodata."))
     return ".rodata";
   if (S.startswith(".data."))
     return ".data";
   if (S.startswith(".bss."))
     return ".bss";
   return S;
 }
 
+template <class ELFT>
+bool Writer<ELFT>::isDiscarded(InputSectionBase<ELFT> *IS) const {
+  if (!IS || !IS->isLive() || IS == &InputSection<ELFT>::Discarded)
+    return true;
+  return InputToOutputSection.lookup(IS->getSectionName()) == "/DISCARD/";
+}
+
+template <class ELFT>
+static bool compareSections(OutputSectionBase<ELFT> *A,
+                            OutputSectionBase<ELFT> *B) {
+  auto ItA = Config->OutputSections.find(A->getName());
+  auto ItEnd = std::end(Config->OutputSections);
+  if (ItA == ItEnd)
+    return compareOutputSections(A, B);
+  auto ItB = Config->OutputSections.find(B->getName());
+  if (ItB == ItEnd)
+    return compareOutputSections(A, B);
+
+  return std::distance(ItA, ItB) > 0;
+}
+
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::createSections() {
   // .interp needs to be on the first page in the output file.
   if (needsInterpSection())
     OutputSections.push_back(Out<ELFT>::Interp);
 
   SmallDenseMap<SectionKey<ELFT::Is64Bits>, OutputSectionBase<ELFT> *> Map;
 
   std::vector<OutputSectionBase<ELFT> *> RegularSections;
 
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab.getObjectFiles()) {
     for (InputSectionBase<ELFT> *C : F->getSections()) {
-      if (!C || !C->isLive() || C == &InputSection<ELFT>::Discarded)
+      if (isDiscarded(C))
         continue;
       const Elf_Shdr *H = C->getSectionHdr();
       uintX_t OutFlags = H->sh_flags & ~SHF_GROUP;
       // For SHF_MERGE we create different output sections for each sh_entsize.
       // This makes each output section simple and keeps a single level
       // mapping from input to output.
       typename InputSectionBase<ELFT>::Kind K = C->SectionKind;
       uintX_t EntSize = K != InputSectionBase<ELFT>::Merge ? 0 : H->sh_entsize;
       uint32_t OutType = H->sh_type;
       if (OutType == SHT_PROGBITS && C->getSectionName() == ".eh_frame" &&
           Config->EMachine == EM_X86_64)
         OutType = SHT_X86_64_UNWIND;
-      SectionKey<ELFT::Is64Bits> Key{getOutputName(C->getSectionName()),
+      SectionKey<ELFT::Is64Bits> Key{getOutputSectionName(C->getSectionName()),
                                      OutType, OutFlags, EntSize};
       OutputSectionBase<ELFT> *&Sec = Map[Key];
       if (!Sec) {
         switch (K) {
         case InputSectionBase<ELFT>::Regular:
           Sec = new (SecAlloc.Allocate())
               OutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
           break;
template <class ELFT> void Writer<ELFT>::createSections() {
   // __tls_get_addr, so it's not defined anywhere. Create a hidden definition
   // to avoid the undefined symbol error.
   if (!isOutputDynamic())
     Symtab.addIgnoredSym("__tls_get_addr");
 
   // Scan relocations. This must be done after every symbol is declared so that
   // we can correctly decide if a dynamic relocation is needed.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab.getObjectFiles()) {
-    for (InputSectionBase<ELFT> *B : F->getSections()) {
-      if (auto *S = dyn_cast_or_null<InputSection<ELFT>>(B)) {
-        if (S != &InputSection<ELFT>::Discarded && S->isLive())
-          scanRelocs(*S);
-      } else if (auto *S = dyn_cast_or_null<EHInputSection<ELFT>>(B)) {
+    for (InputSectionBase<ELFT> *C : F->getSections()) {
+      if (isDiscarded(C))
+        continue;
+      if (auto *S = dyn_cast<InputSection<ELFT>>(C))
+      else if (auto *S = dyn_cast<EHInputSection<ELFT>>(C))
         if (S->RelocSection)
           scanRelocs(*S, *S->RelocSection);
-      }
-    }
-  }
 
   std::vector<DefinedCommon<ELFT> *> CommonSymbols;
   std::vector<SharedSymbol<ELFT> *> SharedCopySymbols;
   for (auto &P : Symtab.getSymbols()) {
     SymbolBody *Body = P.second->Body;
     if (auto *U = dyn_cast<Undefined<ELFT>>(Body))
       if (!U->isWeak() && !U->canKeepUndefined())
         reportUndefined<ELFT>(Symtab, *Body);
if (!Out<ELFT>::Got->empty() ||
       (isOutputDynamic() && Config->EMachine == EM_MIPS))
     OutputSections.push_back(Out<ELFT>::Got);
   if (Out<ELFT>::GotPlt && !Out<ELFT>::GotPlt->empty())
     OutputSections.push_back(Out<ELFT>::GotPlt);
   if (!Out<ELFT>::Plt->empty())
     OutputSections.push_back(Out<ELFT>::Plt);
 
   std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                   compareOutputSections<ELFT>);
+                   compareSections<ELFT>);
 
   for (unsigned I = 0, N = OutputSections.size(); I < N; ++I)
     OutputSections[I]->SectionIndex = I + 1;
 
   for (OutputSectionBase<ELFT> *Sec : OutputSections)
     Out<ELFT>::ShStrTab->add(Sec->getName());
 
   // Finalizers fix each section's size.
void Writer<ELFT>::copyPhdr(Elf_Phdr *PH, OutputSectionBase<ELFT> *From) {
   PH->p_offset = From->getFileOff();
   PH->p_vaddr = From->getVA();
   PH->p_paddr = From->getVA();
   PH->p_filesz = From->getSize();
   PH->p_memsz = From->getSize();
   PH->p_align = From->getAlign();
 }
 
+template <class ELFT> void Writer<ELFT>::buildSectionMap() {
+  for (const std::pair<StringRef, std::vector<StringRef>> &OutSec :
+       Config->OutputSections)
+    for (StringRef Name : OutSec.second)
+      InputToOutputSection[Name] = OutSec.first;
+}
+
 template void lld::elf2::writeResult<ELF32LE>(SymbolTable<ELF32LE> *Symtab);
 template void lld::elf2::writeResult<ELF32BE>(SymbolTable<ELF32BE> *Symtab);
 template void lld::elf2::writeResult<ELF64LE>(SymbolTable<ELF64LE> *Symtab);
 template void lld::elf2::writeResult<ELF64BE>(SymbolTable<ELF64BE> *Symtab);

lld/trunk/test/elf2/linkerscript-sections.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# Empty SECTIONS command.
+# RUN: echo "SECTIONS {}" > %t.script
+# RUN: ld.lld2 -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | \
+# RUN:   FileCheck -check-prefix=SEC-DEFAULT %s
+
+# SECTIONS command with the same order as default.
+# RUN: echo "SECTIONS { \
+# RUN:          .text : { *(.text) } \
+# RUN:          .data : { *(.data) } }" \ > %t.script
+# RUN: ld.lld2 -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: 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:          .shstrtab : { *(.shstrtab) } \
+# RUN:          .symtab : { *(.symtab) } \
+# RUN:          .strtab : { *(.strtab) } \
+# RUN:          .data : { *(.data) } \
+# RUN:          .text : { *(.text) } }" \ > %t.script
+# RUN: ld.lld2 -o %t3 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t3 | \
+# RUN:   FileCheck -check-prefix=SEC-ORDER %s
+
+#           Idx Name          Size
+# SEC-ORDER: 1 .bss          00000002 {{[0-9a-f]*}} BSS
+# SEC-ORDER: 2 other         00000003 {{[0-9a-f]*}} DATA
+# SEC-ORDER: 3 .shstrtab     00000002 {{[0-9a-f]*}}
+# SEC-ORDER: 4 .shstrtab     00000032 {{[0-9a-f]*}}
+# SEC-ORDER: 5 .symtab       00000030 {{[0-9a-f]*}}
+# SEC-ORDER: 6 .strtab       00000008 {{[0-9a-f]*}}
+# SEC-ORDER: 7 .data         00000020 {{[0-9a-f]*}} DATA
+# SEC-ORDER: 8 .text         0000000e {{[0-9a-f]*}} TEXT DATA
+
+# .text and .data have swapped names but proper sizes and types.
+# RUN: echo "SECTIONS { \
+# RUN:          .data : { *(.text) } \
+# RUN:          .text : { *(.data) } }" \ > %t.script
+# RUN: ld.lld2 -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: 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.lld2 -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.lld2 -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