[ELF] Make MergeInputSection merging aware of output sections

[MaskRay]

Summary

Fixes PR38748

mergeSections() calls getOutputSectionName() to get output section
names. Two MergeInputSections may be merged even if they are made
different by SECTIONS commands.

This patch moves mergeSections() after processSectionCommands() and
addOrphanSections() to fix the issue. The new pass is renamed to
OutputSection::finalizeInputSections().

processSectionCommands() and addorphanSections() are changed to add
sections to InputSectionDescription::sectionBases.

finalizeInputSections() merges MergeInputSections and migrates
sectionBases to sections.

For the -r case, we drop an optimization that tries keeping sh_entsize
non-zero. This is for the simplicity of addOrphanSections(). The
updated merge-entsize2.s reflects the change.

[MaskRay]

Delete unrelated InputSectionIterator (I tried changing InputSectionDescription::sections from an InputSection* vector to InputSectionBase* vector, but the result is not clean - many subsequent passes assume the elements of sections are InputSections. The size of OutputSection is not a big concern, so I added another field instead)

Fix a comment.

Add llvm::erase_if(inputSections, [](InputSectionBase *s) { return isa<MergeInputSection>(s); }); to fix an assetion failure

[MaskRay]

Two passes assign InputSectionBases to OutputSections:

• processSectionCommands() calls createInputSectionList to append elements to InputSectionDescription::sectionBases
• addOrphanSections() calls OutputSection::recordSections() to append elements to InputSectionDescription::sectionBases The change also removes an use of SectionBase::assigned, which will enable a further simplication: D67531.

After an InputSectionBase is added to InputSectionDescription::sectionBases: if it is an InputSection, it will go directly to InputSectionDescription::sections; if it is a MergeInputSection, it will be merged with other MergeInputSections to form a MergeSyntheticSection, then the MergeSyntheticSection (a second-order derived class of InputSection) will be appended to InputSectionDescription::sections.

[grimar]

Generally the approach looks good to me. Lets see what other think.

ELF/LinkerScript.h

171 ↗

(On Diff #219936)

These 2 needs comment then I think.

test/ELF/linkerscript/merge-output-sections.s

23 ↗

(On Diff #219936)

Can you use --implicit-check-not=section instead (here and above)?

[peter.smith]

I agree that we'll need something like this for string merging to be used on many embedded systems. I'm a bit concerned about having two semi-parallel vectors sectionBases and sections as we've got some redundancy there and that could lead to problems. At the moment sectionBases is only used for a small part of the link, yet as we don't empty it, it could be used by mistake later on instead of sections. If having two vectors is unavoidable then we should be clear on what the policy is for using one or the other. If we only intend sectionBases to be used for a short time, I'd empty them or prevent them from being used once we're done with them.

ELF/Driver.cpp

1927 ↗

(On Diff #219936)

To me the most important thing here is sectionBases is no longer used after this point.
I suggest something like:
Migrate the sectionBases to sections. This includes merging MergeInputSections into a single MergeSyntheticSection. From this point onwards OutputSection::sections should be used instead of OutputSection::sectionBases should not.

Alternatively explicitly emptying the sectionBases would work.
sec->sectionBases.empty();

ELF/LinkerScript.h

171 ↗

(On Diff #219936)

Agreed. One thing that this does do is introduce a section of Driver.cpp where we should use sectionBases and after the merge only sections. This is difficult to discover and we'll need to be careful to catch people using the wrong one.

ELF/Relocations.cpp

572 ↗

(On Diff #219936)

I think it will be worth a comment, to state that we are adding a section after sectionBases has been transferred to sections

573 ↗

(On Diff #219936)

Unless I'm missing something, won't recordSection(sec) have done the equivalent of:

if (osec->sectionCommands.empty() ||
   !isa<InputSectionDescription>(osec->sectionCommands.back()))
 osec->sectionCommands.push_back(make<InputSectionDescription>(""));

So you could replace with?

auto *isd = cast<InputSectionDescription>(osec->sectionCommands.back());
isd->sections.push_back(sec);

Or if sectionBases is not used beyond this point perhaps don't call osec->recordSection(sec).

[MaskRay]

Thanks for the review!

Applied suggestions.

[peter.smith]

Thanks for the updates. I've made a few suggestions about adding comments to define what addSection and recordSection do and when they should be used, and in the case of addSection what they should be called. I also think that there may be a case for a postFinalizeAddSection(InputSection *isec) function to do the actions that we are inlining for the copyRelocations on Relocations.cpp:570. This would make it easier to know what was needed for any other InputSections that needed to be added later.

ELF/OutputSections.cpp

85 ↗

(On Diff #220108)

The names recordSection() and addSection() are very close, and at first glance it can be difficult to know what the responsibilities of each of the functions are and when it is appropriate to call them.

"Record that isec will be placed in this OutputSection. This does not become permanent until finalizeInputSections is called. It should not be used after finalizeInputSections is called, if you need to add an InputSection post finalizeInputSections, then you must do the following:

• Find or create an InputSectionDescription to hold InputSection.
• Add the InputSection to the InputSectionDesciption::sections
• Det the OutputSection partition.
• Call addSection(isec) to commit the section."

96 ↗

(On Diff #220108)

I don't think that function's name is matching what it does anymore. Maybe something like commitSection. It looks to be doing:

• Initializing or checking flags are consistent with other InputSections.
• Updating the type and flags.
• Updating the alignment.

ELF/Relocations.cpp

574 ↗

(On Diff #220108)

One thing we might not have done is set osec->partition if it hasn't been done already. This is something that recordSection() does.

[MaskRay]

Add comments

[MaskRay]

ELF/Driver.cpp

1927 ↗

(On Diff #219936)

Alternatively explicitly emptying the sectionBases would work.

In finalizeInputSections(): cmd->sectionBases.clear();

This has already been done. I agree this point should be highlighted, and thanks for the wording!

it could be used by mistake later on instead of sections.

cmd->sectionBases.clear(); should detect such mistakes immediately.

ELF/OutputSections.cpp

85 ↗

(On Diff #220108)

Thanks a lot for the suggestion!

Delete the OutputSection partition.

I'll delete this step. partition = isec->partition; is here because LinkerScript.cpp:addInputSec ~L641 checks whether an existing OutputSection can be reused by a new orphan section.

TinyPtrVector<OutputSection *> &v = map[outsecName];
for (OutputSection *sec : v) {
  if (sec->partition != isec->partition) /// checks partition
    continue;
  sec->recordSection(isec);
  return nullptr;
}

So we have to initialize the partition early.

In Relocations.cpp, I'll reorder osec->commitSection(sec); to be the last step to keep consistent with the comment. (osec->commitSection(sec); can be either the first or the last step).

ELF/Relocations.cpp

573 ↗

(On Diff #219936)

Omitting osec->recordSection(sec) should be better.

574 ↗

(On Diff #220108)

bss and bssRelRo are not specific to a partition:

// Linker generated sections which can be used as inputs and are not specific to
// a partition.
struct InStruct {
  InputSection *armAttributes;
  BssSection *bss;
  BssSection *bssRelRo;

I think copy relocations from all paritions share the same .bss or .bss.rel.o in the main partition. Though, I'm not sure if the ld.so implementation has considered the interaction between partitions and copy relocations. @pcc In any case, the patch shouldn't change the behavior here.

[peter.smith]

Thanks for the update. I don't have any more comments at the moment, I'm in favour of making the change. It would be useful to get the perspective of someone coming to the patch for the first time to see if it was easy for them to understand. A possible alternative would be to filter out the MergeInputSections into a separate list. Assign all the other InputSections as before. Then work out where the MergeSyntheticSections would go, create them and insert them into the OutputSections. However I don't think that would be obviously any better.

[MaskRay]

In D67504#1672620, @peter.smith wrote:

Thanks for the update. I don't have any more comments at the moment, I'm in favour of making the change. It would be useful to get the perspective of someone coming to the patch for the first time to see if it was easy for them to understand. A possible alternative would be to filter out the MergeInputSections into a separate list. Assign all the other InputSections as before. Then work out where the MergeSyntheticSections would go, create them and insert them into the OutputSections. However I don't think that would be obviously any better.

Thanks for the review. The problem with 2 lists (one for MergeInputSections that will be merged into MergeSyntheticSections, the other for InputSections) is that the relative positions are significant in the output. If we have 2 lists, sortInputSectionswill become more complex. LinkerScript.cpp:395

// Sort sections as instructed by SORT-family commands and --sort-section
// option. Because SORT-family commands can be nested at most two depth
// (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
...
static void sortInputSections(MutableArrayRef<InputSectionBase *> vec,
                              const SectionPattern &pat) {

[MaskRay]

In D67504#1672620, @peter.smith wrote:

... It would be useful to get the perspective of someone coming to the patch for the first time to see if it was easy for them to understand. ...

@ruiu @grimar 🤔

[grimar]

LGTM

[andrewng]

This change has caused some regressions in some of our local testing. I've filed the bug PR43461 (https://bugs.llvm.org/show_bug.cgi?id=43461) for the issue.

lld/trunk/ELF/Driver.cpp

if (config->emachine == EM_ARM) {
     // FIXME: These warnings can be removed when lld only uses these features
     // when the input objects have been compiled with an architecture that
     // supports them.
     if (config->armHasBlx == false)
       warn("lld uses blx instruction, no object with architecture supporting "
            "feature detected");
   }
 
-  // This adds a .comment section containing a version string. We have to add it
-  // before mergeSections because the .comment section is a mergeable section.
+  // This adds a .comment section containing a version string.
   if (!config->relocatable)
     inputSections.push_back(createCommentSection());
 
   // Replace common symbols with regular symbols.
   replaceCommonSymbols();
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
   splitSections<ELFT>();
   markLive<ELFT>();
   demoteSharedSymbols();
-  mergeSections();
 
   // Make copies of any input sections that need to be copied into each
   // partition.
   copySectionsIntoPartitions();
 
   // Create synthesized sections such as .got and .plt. This is called before
   // processSectionCommands() so that they can be placed by SECTIONS commands.
   createSyntheticSections<ELFT>();
 
   // Some input sections that are used for exception handling need to be moved
   // into synthetic sections. Do that now so that they aren't assigned to
   // output sections in the usual way.
   if (!config->relocatable)
     combineEhSections();
 
   // Create output sections described by SECTIONS commands.
   script->processSectionCommands();
 
   // Linker scripts control how input sections are assigned to output sections.
   // Input sections that were not handled by scripts are called "orphans", and
   // they are assigned to output sections by the default rule. Process that.
   script->addOrphanSections();
 
+  // Migrate InputSectionDescription::sectionBases to sections. This includes
+  // merging MergeInputSections into a single MergeSyntheticSection. From this
+  // point onwards InputSectionDescription::sections should be used instead of
+  // sectionBases.
+  for (BaseCommand *base : script->sectionCommands)
+    if (auto *sec = dyn_cast<OutputSection>(base))
+      sec->finalizeInputSections();
+  llvm::erase_if(inputSections,
+                 [](InputSectionBase *s) { return isa<MergeInputSection>(s); });
+
   // Two input sections with different output sections should not be folded.
   // ICF runs after processSectionCommands() so that we know the output sections.
   if (config->icf != ICFLevel::None) {
     findKeepUniqueSections<ELFT>(args);
     doIcf<ELFT>();
   }
 
   // Read the callgraph now that we know what was gced or icfed

lld/trunk/ELF/LinkerScript.h

struct InputSectionDescription : BaseCommand {
   }
 
   StringMatcher filePat;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> sectionPatterns;
 
+  // Includes InputSections and MergeInputSections. Used temporarily during
+  // assignment of input sections to output sections.
+  std::vector<InputSectionBase *> sectionBases;
+
+  // Used after the finalizeInputSections() pass. MergeInputSections have been
+  // merged into MergeSyntheticSections.
   std::vector<InputSection *> sections;
 
   // Temporary record of synthetic ThunkSection instances and the pass that
   // they were created in. This is used to insert newly created ThunkSections
   // into Sections at the end of a createThunks() pass.
   std::vector<std::pair<ThunkSection *, uint32_t>> thunkSections;
 };
 
class LinkerScript final {
   llvm::DenseMap<StringRef, OutputSection *> nameToOutputSection;
 
   void addSymbol(SymbolAssignment *cmd);
   void assignSymbol(SymbolAssignment *cmd, bool inSec);
   void setDot(Expr e, const Twine &loc, bool inSec);
   void expandOutputSection(uint64_t size);
   void expandMemoryRegions(uint64_t size);
 
-  std::vector<InputSection *>
+  std::vector<InputSectionBase *>
   computeInputSections(const InputSectionDescription *);
 
-  std::vector<InputSection *> createInputSectionList(OutputSection &cmd);
+  std::vector<InputSectionBase *> createInputSectionList(OutputSection &cmd);
 
   std::vector<size_t> getPhdrIndices(OutputSection *sec);
 
   MemoryRegion *findMemoryRegion(OutputSection *sec);
 
   void switchTo(OutputSection *sec);
   uint64_t advance(uint64_t size, unsigned align);
   void output(InputSection *sec);
class LinkerScript final {
   uint64_t dot;
 
 public:
   OutputSection *createOutputSection(StringRef name, StringRef location);
   OutputSection *getOrCreateOutputSection(StringRef name);
 
   bool hasPhdrsCommands() { return !phdrsCommands.empty(); }
   uint64_t getDot() { return dot; }
-  void discard(ArrayRef<InputSection *> v);
+  void discard(InputSectionBase *s);
 
   ExprValue getSymbolValue(StringRef name, const Twine &loc);
 
   void addOrphanSections();
   void adjustSectionsBeforeSorting();
   void adjustSectionsAfterSorting();
 
   std::vector<PhdrEntry *> createPhdrs();

lld/trunk/ELF/LinkerScript.cpp

for (InputSectionDescription *id : keptSections)
     if (id->filePat.match(filename))
       for (SectionPattern &p : id->sectionPatterns)
         if (p.sectionPat.match(s->name))
           return true;
   return false;
 }
 
 // A helper function for the SORT() command.
-static bool matchConstraints(ArrayRef<InputSection *> sections,
+static bool matchConstraints(ArrayRef<InputSectionBase *> sections,
                              ConstraintKind kind) {
   if (kind == ConstraintKind::NoConstraint)
     return true;
 
   bool isRW = llvm::any_of(
-      sections, [](InputSection *sec) { return sec->flags & SHF_WRITE; });
+      sections, [](InputSectionBase *sec) { return sec->flags & SHF_WRITE; });
 
   return (isRW && kind == ConstraintKind::ReadWrite) ||
          (!isRW && kind == ConstraintKind::ReadOnly);
 }
 
-static void sortSections(MutableArrayRef<InputSection *> vec,
+static void sortSections(MutableArrayRef<InputSectionBase *> vec,
                          SortSectionPolicy k) {
   auto alignmentComparator = [](InputSectionBase *a, InputSectionBase *b) {
     // ">" is not a mistake. Sections with larger alignments are placed
     // before sections with smaller alignments in order to reduce the
     // amount of padding necessary. This is compatible with GNU.
     return a->alignment > b->alignment;
   };
   auto nameComparator = [](InputSectionBase *a, InputSectionBase *b) {

 // line option is respected even if a SORT command is given, the exact
 // behavior we have here is a bit complicated. Here are the rules.
 //
 // 1. If two SORT commands are given, --sort-section is ignored.
 // 2. If one SORT command is given, and if it is not SORT_NONE,
 //    --sort-section is handled as an inner SORT command.
 // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
 // 4. If no SORT command is given, sort according to --sort-section.
-static void sortInputSections(MutableArrayRef<InputSection *> vec,
+static void sortInputSections(MutableArrayRef<InputSectionBase *> vec,
                               const SectionPattern &pat) {
   if (pat.sortOuter == SortSectionPolicy::None)
     return;
 
   if (pat.sortInner == SortSectionPolicy::Default)
     sortSections(vec, config->sortSection);
   else
     sortSections(vec, pat.sortInner);
   sortSections(vec, pat.sortOuter);
 }
 
 // Compute and remember which sections the InputSectionDescription matches.
-std::vector<InputSection *>
+std::vector<InputSectionBase *>
 LinkerScript::computeInputSections(const InputSectionDescription *cmd) {
-  std::vector<InputSection *> ret;
+  std::vector<InputSectionBase *> ret;
 
   // Collects all sections that satisfy constraints of Cmd.
   for (const SectionPattern &pat : cmd->sectionPatterns) {
     size_t sizeBefore = ret.size();
 
     for (InputSectionBase *sec : inputSections) {
       if (!sec->isLive() || sec->assigned)
         continue;
 
       // For -emit-relocs we have to ignore entries like
       //   .rela.dyn : { *(.rela.data) }
       // which are common because they are in the default bfd script.
       // We do not ignore SHT_REL[A] linker-synthesized sections here because
       // want to support scripts that do custom layout for them.
-      //
-      // It is safe to assume that Sec is an InputSection because mergeable or
-      // EH input sections have already been handled and eliminated.
-      if (cast<InputSection>(sec)->getRelocatedSection())
+      if (isa<InputSection>(sec) &&
+          cast<InputSection>(sec)->getRelocatedSection())
         continue;
 
       std::string filename = getFilename(sec->file);
       if (!cmd->filePat.match(filename) ||
           pat.excludedFilePat.match(filename) ||
           !pat.sectionPat.match(sec->name))
         continue;
 
-      ret.push_back(cast<InputSection>(sec));
+      ret.push_back(sec);
       sec->assigned = true;
     }
 
-    sortInputSections(MutableArrayRef<InputSection *>(ret).slice(sizeBefore),
-                      pat);
+    sortInputSections(
+        MutableArrayRef<InputSectionBase *>(ret).slice(sizeBefore), pat);
   }
   return ret;
 }
 
-void LinkerScript::discard(ArrayRef<InputSection *> v) {
-  for (InputSection *s : v) {
-    if (s == in.shStrTab || s == mainPart->relaDyn || s == mainPart->relrDyn)
-      error("discarding " + s->name + " section is not allowed");
+void LinkerScript::discard(InputSectionBase *s) {
 
-    // You can discard .hash and .gnu.hash sections by linker scripts. Since
-    // they are synthesized sections, we need to handle them differently than
-    // other regular sections.
-    if (s == mainPart->gnuHashTab)
-      mainPart->gnuHashTab = nullptr;
-    if (s == mainPart->hashTab)
-      mainPart->hashTab = nullptr;
 
-    s->markDead();
-    discard(s->dependentSections);
-  }
+  for (InputSection *ds : s->dependentSections)
+    discard(ds);
 }
 
-std::vector<InputSection *>
+std::vector<InputSectionBase *>
 LinkerScript::createInputSectionList(OutputSection &outCmd) {
-  std::vector<InputSection *> ret;
+  std::vector<InputSectionBase *> ret;
 
   for (BaseCommand *base : outCmd.sectionCommands) {
     if (auto *cmd = dyn_cast<InputSectionDescription>(base)) {
-      cmd->sections = computeInputSections(cmd);
-      ret.insert(ret.end(), cmd->sections.begin(), cmd->sections.end());
+      cmd->sectionBases = computeInputSections(cmd);
+      ret.insert(ret.end(), cmd->sectionBases.begin(), cmd->sectionBases.end());
     }
   }
   return ret;
 }
 
 // Create output sections described by SECTIONS commands.
 void LinkerScript::processSectionCommands() {
   size_t i = 0;
   for (BaseCommand *base : sectionCommands) {
     if (auto *sec = dyn_cast<OutputSection>(base)) {
-      std::vector<InputSection *> v = createInputSectionList(*sec);
+      std::vector<InputSectionBase *> v = createInputSectionList(*sec);
 
       // The output section name `/DISCARD/' is special.
       // Any input section assigned to it is discarded.
       if (sec->name == "/DISCARD/") {
-        discard(v);
+        for (InputSectionBase *s : v)
+          discard(s);
         sec->sectionCommands.clear();
         continue;
       }
 
       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
       // sections satisfy a given constraint. If not, a directive is handled
       // as if it wasn't present from the beginning.
if (auto *sec = dyn_cast<OutputSection>(base)) {
       // is given, input sections are aligned to that value, whether the
       // given value is larger or smaller than the original section alignment.
       if (sec->subalignExpr) {
         uint32_t subalign = sec->subalignExpr().getValue();
         for (InputSectionBase *s : v)
           s->alignment = subalign;
       }
 
-      // Some input sections may be removed from the list after ICF.
-      for (InputSection *s : v)
-        sec->addSection(s);
-
       sec->sectionIndex = i++;
-      if (sec->noload)
-        sec->type = SHT_NOBITS;
-      if (sec->nonAlloc)
-        sec->flags &= ~(uint64_t)SHF_ALLOC;
+      for (InputSectionBase *s : v)
+        s->parent = sec;
     }
   }
 }
 
 void LinkerScript::processSymbolAssignments() {
   // Dot outside an output section still represents a relative address, whose
   // sh_shndx should not be SHN_UNDEF or SHN_ABS. Create a dummy aether section
   // that fills the void outside a section. It has an index of one, which is
if (auto *sec = dyn_cast<OutputSection>(base))
       if (sec->name == name)
         return sec;
   return nullptr;
 }
 
 static OutputSection *createSection(InputSectionBase *isec,
                                     StringRef outsecName) {
   OutputSection *sec = script->createOutputSection(outsecName, "<internal>");
-  sec->addSection(cast<InputSection>(isec));
+  sec->recordSection(isec);
   return sec;
 }
 
 static OutputSection *
 addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
             InputSectionBase *isec, StringRef outsecName) {
   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
   // option is given. A section with SHT_GROUP defines a "section group", and
addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
   // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
   // other REL[A] sections created by linker itself.
   if (!isa<SyntheticSection>(isec) &&
       (isec->type == SHT_REL || isec->type == SHT_RELA)) {
     auto *sec = cast<InputSection>(isec);
     OutputSection *out = sec->getRelocatedSection()->getOutputSection();
 
     if (out->relocationSection) {
-      out->relocationSection->addSection(sec);
+      out->relocationSection->recordSection(sec);
       return nullptr;
     }
 
     out->relocationSection = createSection(isec, outsecName);
     return out->relocationSection;
   }
 
-  // When control reaches here, mergeable sections have already been merged into
-  // synthetic sections. For relocatable case we want to create one output
-  // section per syntetic section so that they have a valid sh_entsize.
-  if (config->relocatable && (isec->flags & SHF_MERGE))
-    return createSection(isec, outsecName);
-
   //  The ELF spec just says
   // ----------------------------------------------------------------
   // In the first phase, input sections that match in name, type and
   // attribute flags should be concatenated into single sections.
   // ----------------------------------------------------------------
   //
   // However, it is clear that at least some flags have to be ignored for
   // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
   // and end symbols.
   //
   // Given the above issues, we instead merge sections by name and error on
   // incompatible types and flags.
   TinyPtrVector<OutputSection *> &v = map[outsecName];
   for (OutputSection *sec : v) {
     if (sec->partition != isec->partition)
       continue;
-    sec->addSection(cast<InputSection>(isec));
+    sec->recordSection(isec);
     return nullptr;
   }
 
   OutputSection *sec = createSection(isec, outsecName);
   v.push_back(sec);
   return sec;
 }
 
auto add = [&](InputSectionBase *s) {
     StringRef name = getOutputSectionName(s);
 
     if (config->orphanHandling == OrphanHandlingPolicy::Error)
       error(toString(s) + " is being placed in '" + name + "'");
     else if (config->orphanHandling == OrphanHandlingPolicy::Warn)
       warn(toString(s) + " is being placed in '" + name + "'");
 
     if (OutputSection *sec = findByName(sectionCommands, name)) {
-      sec->addSection(cast<InputSection>(s));
+      sec->recordSection(s);
       return;
     }
 
     if (OutputSection *os = addInputSec(map, s, name))
       v.push_back(os);
-    assert(s->getOutputSection()->sectionIndex == UINT32_MAX);
+    assert(isa<MergeInputSection>(s) ||
+           s->getOutputSection()->sectionIndex == UINT32_MAX);
   };
 
   // For futher --emit-reloc handling code we need target output section
   // to be created before we create relocation output section, so we want
   // to create target sections first. We do not want priority handling
   // for synthetic sections because them are special.
   for (InputSectionBase *isec : inputSections) {
     if (auto *sec = dyn_cast<InputSection>(isec))

lld/trunk/ELF/OutputSections.h

public:
   // corresponds to the Elf_Shdr member.
   uint64_t size = 0;
 
   // The following fields correspond to Elf_Shdr members.
   uint64_t offset = 0;
   uint64_t addr = 0;
   uint32_t shName = 0;
 
-  void addSection(InputSection *isec);
+  void recordSection(InputSectionBase *isec);
+  void commitSection(InputSection *isec);
+  void finalizeInputSections();
 
   // The following members are normally only used in linker scripts.
   MemoryRegion *memRegion = nullptr;
   MemoryRegion *lmaRegion = nullptr;
   Expr addrExpr;
   Expr alignExpr;
   Expr lmaExpr;
   Expr subalignExpr;

lld/trunk/ELF/OutputSections.cpp

 // any special treatment on top of progbits, so there doesn't
 // seem to be a harm in merging them.
 static bool canMergeToProgbits(unsigned type) {
   return type == SHT_NOBITS || type == SHT_PROGBITS || type == SHT_INIT_ARRAY ||
          type == SHT_PREINIT_ARRAY || type == SHT_FINI_ARRAY ||
          type == SHT_NOTE;
 }
 
-void OutputSection::addSection(InputSection *isec) {
+// Record that isec will be placed in the OutputSection. isec does not become
+// permanent until finalizeInputSections() is called. The function should not be
+// used after finalizeInputSections() is called. If you need to add an
+// InputSection post finalizeInputSections(), then you must do the following:
+//
+// 1. Find or create an InputSectionDescription to hold InputSection.
+// 2. Add the InputSection to the InputSectionDesciption::sections.
+// 3. Call commitSection(isec).
+void OutputSection::recordSection(InputSectionBase *isec) {
+  partition = isec->partition;
+  isec->parent = this;
+  if (sectionCommands.empty() ||
+      !isa<InputSectionDescription>(sectionCommands.back()))
+    sectionCommands.push_back(make<InputSectionDescription>(""));
+  auto *isd = cast<InputSectionDescription>(sectionCommands.back());
+  isd->sectionBases.push_back(isec);
+}
+
+// Update fields (type, flags, alignment, etc) according to the InputSection
+// isec. Also check whether the InputSection flags and type are consistent with
+// other InputSections.
+void OutputSection::commitSection(InputSection *isec) {
   if (!hasInputSections) {
     // If IS is the first section to be added to this section,
-    // initialize Partition, Type, Entsize and flags from IS.
+    // initialize type, entsize and flags from isec.
     hasInputSections = true;
-    partition = isec->partition;
     type = isec->type;
     entsize = isec->entsize;
     flags = isec->flags;
   } else {
     // Otherwise, check if new type or flags are compatible with existing ones.
     unsigned mask = SHF_TLS | SHF_LINK_ORDER;
     if ((flags & mask) != (isec->flags & mask))
       error("incompatible section flags for " + name + "\n>>> " + toString(isec) +
             ": 0x" + utohexstr(isec->flags) + "\n>>> output section " + name +
             ": 0x" + utohexstr(flags));
 
     if (type != isec->type) {
       if (!canMergeToProgbits(type) || !canMergeToProgbits(isec->type))
         error("section type mismatch for " + isec->name + "\n>>> " +
               toString(isec) + ": " +
               getELFSectionTypeName(config->emachine, isec->type) +
               "\n>>> output section " + name + ": " +
               getELFSectionTypeName(config->emachine, type));
       type = SHT_PROGBITS;
     }
   }
+  if (noload)
+    type = SHT_NOBITS;
 
   isec->parent = this;
   uint64_t andMask =
       config->emachine == EM_ARM ? (uint64_t)SHF_ARM_PURECODE : 0;
   uint64_t orMask = ~andMask;
   uint64_t andFlags = (flags & isec->flags) & andMask;
   uint64_t orFlags = (flags | isec->flags) & orMask;
   flags = andFlags | orFlags;
+  if (nonAlloc)
+    flags &= ~(uint64_t)SHF_ALLOC;
 
   alignment = std::max(alignment, isec->alignment);
 
   // If this section contains a table of fixed-size entries, sh_entsize
   // holds the element size. If it contains elements of different size we
   // set sh_entsize to 0.
   if (entsize != isec->entsize)
     entsize = 0;
+}
 
-  if (!isec->assigned) {
-    isec->assigned = true;
-    if (sectionCommands.empty() ||
-        !isa<InputSectionDescription>(sectionCommands.back()))
-      sectionCommands.push_back(make<InputSectionDescription>(""));
-    auto *isd = cast<InputSectionDescription>(sectionCommands.back());
-    isd->sections.push_back(isec);
+// This function scans over the InputSectionBase list sectionBases to create
+// InputSectionDescription::sections.
+//
+// It removes MergeInputSections from the input section array and adds
+// new synthetic sections at the location of the first input section
+// that it replaces. It then finalizes each synthetic section in order
+// to compute an output offset for each piece of each input section.
+void OutputSection::finalizeInputSections() {
+  std::vector<MergeSyntheticSection *> mergeSections;
+  for (BaseCommand *base : sectionCommands) {
+    auto *cmd = dyn_cast<InputSectionDescription>(base);
+    if (!cmd)
+      continue;
+    cmd->sections.reserve(cmd->sectionBases.size());
+    for (InputSectionBase *s : cmd->sectionBases) {
+      MergeInputSection *ms = dyn_cast<MergeInputSection>(s);
+      if (!ms) {
+        cmd->sections.push_back(cast<InputSection>(s));
+        continue;
+      }
+
+      // We do not want to handle sections that are not alive, so just remove
+      // them instead of trying to merge.
+      if (!ms->isLive())
+        continue;
+
+      auto i = llvm::find_if(mergeSections, [=](MergeSyntheticSection *sec) {
+        // While we could create a single synthetic section for two different
+        // values of Entsize, it is better to take Entsize into consideration.
+        //
+        // With a single synthetic section no two pieces with different Entsize
+        // could be equal, so we may as well have two sections.
+        //
+        // Using Entsize in here also allows us to propagate it to the synthetic
+        // section.
+        //
+        // SHF_STRINGS section with different alignments should not be merged.
+        return sec->flags == ms->flags && sec->entsize == ms->entsize &&
+               (sec->alignment == ms->alignment || !(sec->flags & SHF_STRINGS));
+      });
+      if (i == mergeSections.end()) {
+        MergeSyntheticSection *syn =
+            createMergeSynthetic(name, ms->type, ms->flags, ms->alignment);
+        mergeSections.push_back(syn);
+        i = std::prev(mergeSections.end());
+        syn->entsize = ms->entsize;
+        cmd->sections.push_back(syn);
+      }
+      (*i)->addSection(ms);
+    }
+
+    // sectionBases should not be used from this point onwards. Clear it to
+    // catch misuses.
+    cmd->sectionBases.clear();
+
+    // Some input sections may be removed from the list after ICF.
+    for (InputSection *s : cmd->sections)
+      commitSection(s);
   }
+  for (auto *ms : mergeSections)
+    ms->finalizeContents();
 }
 
 static void sortByOrder(MutableArrayRef<InputSection *> in,
                         llvm::function_ref<int(InputSectionBase *s)> order) {
   std::vector<std::pair<int, InputSection *>> v;
   for (InputSection *s : in)
     v.push_back({order(s), s});
   llvm::stable_sort(v, less_first());

lld/trunk/ELF/Relocations.cpp

template <class ELFT> static void addCopyRelSymbol(SharedSymbol &ss) {
   if (symSize == 0 || ss.alignment == 0)
     fatal("cannot create a copy relocation for symbol " + toString(ss));
 
   // See if this symbol is in a read-only segment. If so, preserve the symbol's
   // memory protection by reserving space in the .bss.rel.ro section.
   bool isRO = isReadOnly<ELFT>(ss);
   BssSection *sec =
       make<BssSection>(isRO ? ".bss.rel.ro" : ".bss", symSize, ss.alignment);
-  if (isRO)
-    in.bssRelRo->getParent()->addSection(sec);
-  else
-    in.bss->getParent()->addSection(sec);
+  OutputSection *osec = (isRO ? in.bssRelRo : in.bss)->getParent();
+
+  // At this point, sectionBases has been migrated to sections. Append sec to
+  // sections.
+  if (osec->sectionCommands.empty() ||
+      !isa<InputSectionDescription>(osec->sectionCommands.back()))
+    osec->sectionCommands.push_back(make<InputSectionDescription>(""));
+  auto *isd = cast<InputSectionDescription>(osec->sectionCommands.back());
+  isd->sections.push_back(sec);
+  osec->commitSection(sec);
 
   // Look through the DSO's dynamic symbol table for aliases and create a
   // dynamic symbol for each one. This causes the copy relocation to correctly
   // interpose any aliases.
   for (SharedSymbol *sym : getSymbolsAt<ELFT>(ss))
     replaceWithDefined(*sym, sec, 0, sym->size);
 
   mainPart->relaDyn->addReloc(target->copyRel, sec, 0, &ss);

lld/trunk/ELF/SyntheticSections.h

public:
   PartitionIndexSection();
   size_t getSize() const override;
   void finalizeContents() override;
   void writeTo(uint8_t *buf) override;
 };
 
 InputSection *createInterpSection();
 MergeInputSection *createCommentSection();
+MergeSyntheticSection *createMergeSynthetic(StringRef name, uint32_t type,
+                                            uint64_t flags, uint32_t alignment);
 template <class ELFT> void splitSections();
-void mergeSections();
 
 template <typename ELFT> void writeEhdr(uint8_t *buf, Partition &part);
 template <typename ELFT> void writePhdrs(uint8_t *buf, Partition &part);
 
 Defined *addSyntheticLocal(StringRef name, uint8_t type, uint64_t value,
                            uint64_t size, InputSectionBase &section);
 
 void addVerneed(Symbol *ss);

lld/trunk/ELF/SyntheticSections.cpp

void MergeNoTailSection::finalizeContents() {
   parallelForEach(sections, [&](MergeInputSection *sec) {
     for (size_t i = 0, e = sec->pieces.size(); i != e; ++i)
       if (sec->pieces[i].live)
         sec->pieces[i].outputOff +=
             shardOffsets[getShardId(sec->pieces[i].hash)];
   });
 }
 
-static MergeSyntheticSection *createMergeSynthetic(StringRef name,
-                                                   uint32_t type,
-                                                   uint64_t flags,
-                                                   uint32_t alignment) {
+MergeSyntheticSection *elf::createMergeSynthetic(StringRef name, uint32_t type,
   bool shouldTailMerge = (flags & SHF_STRINGS) && config->optimize >= 2;
   if (shouldTailMerge)
     return make<MergeTailSection>(name, type, flags, alignment);
   return make<MergeNoTailSection>(name, type, flags, alignment);
 }
 
 template <class ELFT> void elf::splitSections() {
   // splitIntoPieces needs to be called on each MergeInputSection
   // before calling finalizeContents().
   parallelForEach(inputSections, [](InputSectionBase *sec) {
     if (auto *s = dyn_cast<MergeInputSection>(sec))
       s->splitIntoPieces();
     else if (auto *eh = dyn_cast<EhInputSection>(sec))
       eh->split<ELFT>();
   });
 }
 
-// This function scans over the inputsections to create mergeable
-// synthetic sections.
-//
-// It removes MergeInputSections from the input section array and adds
-// new synthetic sections at the location of the first input section
-// that it replaces. It then finalizes each synthetic section in order
-// to compute an output offset for each piece of each input section.
-void elf::mergeSections() {
-  std::vector<MergeSyntheticSection *> mergeSections;
-  for (InputSectionBase *&s : inputSections) {
-    MergeInputSection *ms = dyn_cast<MergeInputSection>(s);
-    if (!ms)
-      continue;
-
-    // We do not want to handle sections that are not alive, so just remove
-    // them instead of trying to merge.
-    if (!ms->isLive()) {
-      s = nullptr;
-      continue;
-    }
-
-    StringRef outsecName = getOutputSectionName(ms);
-
-    auto i = llvm::find_if(mergeSections, [=](MergeSyntheticSection *sec) {
-      // While we could create a single synthetic section for two different
-      // values of Entsize, it is better to take Entsize into consideration.
-      //
-      // With a single synthetic section no two pieces with different Entsize
-      // could be equal, so we may as well have two sections.
-      //
-      // Using Entsize in here also allows us to propagate it to the synthetic
-      // section.
-      //
-      // SHF_STRINGS section with different alignments should not be merged.
-      return sec->name == outsecName && sec->flags == ms->flags &&
-             sec->entsize == ms->entsize &&
-             (sec->alignment == ms->alignment || !(sec->flags & SHF_STRINGS));
-    });
-    if (i == mergeSections.end()) {
-      MergeSyntheticSection *syn =
-          createMergeSynthetic(outsecName, ms->type, ms->flags, ms->alignment);
-      mergeSections.push_back(syn);
-      i = std::prev(mergeSections.end());
-      s = syn;
-      syn->entsize = ms->entsize;
-    } else {
-      s = nullptr;
-    }
-    (*i)->addSection(ms);
-  }
-  for (auto *ms : mergeSections)
-    ms->finalizeContents();
-
-  std::vector<InputSectionBase *> &v = inputSections;
-  v.erase(std::remove(v.begin(), v.end(), nullptr), v.end());
-}
-
 MipsRldMapSection::MipsRldMapSection()
     : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, config->wordsize,
                        ".rld_map") {}
 
 ARMExidxSyntheticSection::ARMExidxSyntheticSection()
     : SyntheticSection(SHF_ALLOC | SHF_LINK_ORDER, SHT_ARM_EXIDX,
                        config->wordsize, ".ARM.exidx") {}
 

lld/trunk/ELF/Writer.cpp

if (!sec)
       continue;
     auto i = llvm::find_if(sec->sectionCommands, [](BaseCommand *base) {
       if (auto *isd = dyn_cast<InputSectionDescription>(base))
         return !isd->sections.empty();
       return false;
     });
     if (i == sec->sectionCommands.end())
       continue;
-    InputSection *isec = cast<InputSectionDescription>(*i)->sections[0];
+    InputSectionBase *isec = cast<InputSectionDescription>(*i)->sections[0];
 
     // Relocations are not using REL[A] section symbols.
     if (isec->type == SHT_REL || isec->type == SHT_RELA)
       continue;
 
     // Unlike other synthetic sections, mergeable output sections contain data
     // copied from input sections, and there may be a relocation pointing to its
     // contents if -r or -emit-reloc are given.

lld/trunk/test/ELF/linkerscript/merge-output-sections.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+## SHF_MERGE sections within the same output section can be freely merged.
+# RUN: echo 'SECTIONS { .rodata : { *(.rodata.*) }}' > %t.script
+# RUN: ld.lld %t.o -T %t.script -o %t
+# RUN: llvm-readelf -x .rodata %t | FileCheck --check-prefix=SAME %s --implicit-check-not=section
+
+# SAME:      section '.rodata':
+# SAME-NEXT: 0x00000000 01000200 0300
+
+## SHF_MERGE sections with different output sections cannot be merged.
+# RUN: echo 'SECTIONS { \
+# RUN:   .rodata.foo : { *(.rodata.foo) } \
+# RUN:   .rodata.bar : { *(.rodata.bar) } \
+# RUN: }' > %t2.script
+# RUN: ld.lld %t.o -T %t2.script -o %t2
+# RUN: llvm-readelf -x .rodata.foo -x .rodata.bar %t2 | FileCheck --check-prefix=DIFF %s --implicit-check-not=section
+
+# DIFF:      section '.rodata.foo':
+# DIFF-NEXT: 0x00000000 01000200 0300
+# DIFF:      section '.rodata.bar':
+# DIFF-NEXT: 0x00000006 0100
+
+.section .rodata.foo,"aM",@progbits,2,unique,0
+.short 1
+.short 2
+.section .rodata.foo,"aM",@progbits,2,unique,1
+.short 1
+.short 3
+
+.section .rodata.bar,"aM",@progbits,2,unique,0
+.short 1
+.section .rodata.bar,"aM",@progbits,2,unique,1
+.short 1

lld/trunk/test/ELF/linkerscript/merge-sections.s

 # CHECK-NEXT:   Type: SHT_PROGBITS
 # CHECK-NEXT:   Flags [
 # CHECK-NEXT:     SHF_ALLOC
 # CHECK-NEXT:     SHF_MERGE
 # CHECK-NEXT:     SHF_STRINGS
 # CHECK-NEXT:   ]
 # CHECK-NEXT:   Address: 0x[[ADDR1:.*]]
 # CHECK-NEXT:   Offset: 0x[[ADDR1]]
-# CHECK-NEXT:   Size: 14
+# CHECK-NEXT:   Size: 8
 # CHECK-NEXT:   Link: 0
 # CHECK-NEXT:   Info: 0
 # CHECK-NEXT:   AddressAlignment: 2
 # CHECK-NEXT:   EntrySize: 0
 # CHECK-NEXT: }
 
 # CHECK:      Name: begin
 # CHECK-NEXT: Value: 0x[[ADDR1]]
 
 # CHECK:      Name: end
-# CHECK-NEXT: Value: 0x236
+# CHECK-NEXT: Value: 0x230
 
 # Check that we don't crash with --gc-sections
 # RUN: ld.lld --gc-sections -o %t2 --script %t.script %t -shared
 # RUN: llvm-readobj -S --symbols %t2 | FileCheck %s --check-prefix=GC
 
 # GC:        Name: .foo
 # GC-NEXT:   Type: SHT_PROGBITS
 # GC-NEXT:   Flags [

lld/trunk/test/ELF/merge-entsize2.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 
 # RUN: ld.lld %t.o -o %t
 # RUN: llvm-readelf -S %t | FileCheck --check-prefix=SEC %s
 # RUN: llvm-readelf -x .cst %t | FileCheck --check-prefix=HEX %s
 
 # RUN: ld.lld -O0 -r %t.o -o %t1.o
-# RUN: llvm-readelf -S %t1.o | FileCheck --check-prefix=SEC-R %s
-# RUN: llvm-readelf -x .cst %t1.o | FileCheck --check-prefix=HEX-R %s
+# RUN: llvm-readelf -S %t1.o | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .cst %t1.o | FileCheck --check-prefix=HEX %s
 
 ## Check that SHF_MERGE sections with the same name, sh_flags and sh_entsize
 ## are grouped together and can be merged within the group.
 
 ## .cst 0 and .cst 1 are merged (sh_entsize=4). The result and .cst 2 and
 ## combined (sh_entsize=8). The output sh_entsize is 0.
 # SEC:   Name  Type     {{.*}} Size   ES Flg Lk Inf Al
 # SEC:   .cst  PROGBITS {{.*}} 000020 00  AM  0   0  8
 
-## .cst 0 and .cst 1 are merged, but emitted as a separate output section.
-# SEC-R: .cst  PROGBITS {{.*}} 00000c 04  AM  0   0  4
-# SEC-R: .cst  PROGBITS {{.*}} 000010 08  AM  0   0  8
-
 # HEX:      Hex dump of section '.cst':
 # HEX-NEXT: 0x{{[0-9a-f]+}} 01000000 00000000 02000000 00000000
 # HEX-NEXT: 0x{{[0-9a-f]+}} 01000000 00000000 03000000 00000000
 
-# HEX-R:      Hex dump of section '.cst':
-# HEX-R-NEXT: 0x00000000 01000000 00000000 02000000
-# HEX-R-EMPTY:
-# HEX-R-NEXT: Hex dump of section '.cst':
-# HEX-R-NEXT: 0x00000000 01000000 00000000 03000000 00000000
-
 .section .cst,"aM",@progbits,4,unique,0
 .align 2
 .long 1
 .long 0
 .long 2
 
 .section .cst,"aM",@progbits,4,unique,1
 .align 4
 .long 1
 .long 0
 .long 2
 
 .section .cst,"aM",@progbits,8,unique,2
 .align 8
 .quad 1
 .quad 3