[ELF] - Use output section prediction when creating mergeable synthetic sections.

[grimar]

Summary

We have a bug "Section merge should match the rules specified in the linker script." (https://bugs.llvm.org//show_bug.cgi?id=38748).
Which says that LLD is unable to handle the following code correctly:

SECTIONS {
  .rodata_fooSec : { *(.rodata.foo) }
  .rodata_barSec : { *(.rodata.bar) }
}

We know about that and it happens because we create mergeable synthetic sections very early, before
parsing the linker script. That allows us to keep the whole linker logic simpler.
I would try not to change that.

What I suggest to do in this patch is to use output section prediction
and do not merge together sections which are going to be placed into different output sections.
That fixes the bug.

Also that fixes merge_sections.s. It turns out currently we missed merging optimization and this patch
fixes it either. That happened because we used output section name for a synthetic section. And script
instructions did not match it. This patch uses the name of the first input section as a name for synthetic
section instead.

There is a room for optimizations can be done here, I would like to see the feedback about the approach first.

[ruiu]

It sounds like a good idea, but still I don't think we want this much complexity. Linker script is a can of warms, and unfortunately it's already half-open in lld, but I'd still like to make an effort push it back to keep the code manageable. If more people come in and claim that they really need this, I'd consider that, but for now the code simplicity seems more important than satisfying the long-tail need.

[NickHung]

Filename matching seems not to be considered in this patch.

A test case for your reference.

SECTIONS {
.rodata_A : { a.o(.rodata.foo) }
.rodata_B : { b.o(.rodata.foo) }
}

[grimar]

In D52459#1246035, @NickHung wrote:

Filename matching seems not to be considered in this patch.

A test case for your reference.

SECTIONS {
.rodata_A : { a.o(.rodata.foo) }
.rodata_B : { b.o(.rodata.foo) }
}

Yes, it was not the intention to support it here. Filename matching should be
not hard to do with this approach though.

[grimar]

Too old.

ELF/LinkerScript.h

class LinkerScript final {
   // LinkerScript.
   AddressState *Ctx = nullptr;
 
   OutputSection *Aether;
 
   uint64_t Dot;
 
 public:
+  std::vector<OutputSection *>
+  predictOutputSections(std::vector<InputSectionBase *> V);
+
   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);
 
   ExprValue getSymbolValue(StringRef Name, const Twine &Loc);

ELF/LinkerScript.cpp

static void sortInputSections(MutableArrayRef<InputSection *> Vec,
 
   if (Pat.SortInner == SortSectionPolicy::Default)
     sortSections(Vec, Config->SortSection);
   else
     sortSections(Vec, Pat.SortInner);
   sortSections(Vec, Pat.SortOuter);
 }
 
+static bool matches(StringRef Name, std::vector<SectionPattern> &V) {
+  for (const SectionPattern &Pat : V)
+    if (Pat.SectionPat.match(Name))
+      return true;
+  return false;
+}
+
+// This function predicts the output section names. For the given list of input
+// sections method returns the list of predicted output sections.
+// It is used for creating mergeable sections and do only basic name matching
+// logic. That allows us to create different output sections if that is
+// specified in the script, but keep the whole linker logic simple, what is
+// possible because we call mergeSections() early. Otherwise, we would need to
+// merge sections during handling the linker script commands and handling orphan
+// sections, that is not that convenient and does not seem to have any valuable
+// benefits for users.
+std::vector<OutputSection *>
+LinkerScript::predictOutputSections(std::vector<InputSectionBase *> V) {
+  if (!Script->HasSectionsCommand)
+    return {};
+
+  std::vector<OutputSection *> Ret(V.size());
+  for (BaseCommand *OutBase : SectionCommands) {
+    if (auto *OS = dyn_cast<OutputSection>(OutBase)) {
+      for (BaseCommand *InBase : OS->SectionCommands) {
+        InputSectionDescription *Cmd =
+            dyn_cast<InputSectionDescription>(InBase);
+        if (!Cmd)
+          continue;
+
+        for (size_t I = 0; I < V.size(); ++I) {
+          if (Ret[I] || !matches(V[I]->Name, Cmd->SectionPatterns))
+            continue;
+          Ret[I] = OS;
+        }
+      }
+    }
+  }
+  return Ret;
+}
+
 // Compute and remember which sections the InputSectionDescription matches.
 std::vector<InputSection *>
 LinkerScript::computeInputSections(const InputSectionDescription *Cmd) {
   std::vector<InputSection *> Ret;
 
   // Collects all sections that satisfy constraints of Cmd.
   for (const SectionPattern &Pat : Cmd->SectionPatterns) {
     size_t SizeBefore = Ret.size();

ELF/SyntheticSections.cpp

 // 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;
+  std::vector<OutputSection *> PredictedOS =
+      Script->predictOutputSections(InputSections);
+  DenseMap<MergeSyntheticSection *, StringRef> SecToOutputName;
+
+  size_t N = 0;
   for (InputSectionBase *&S : InputSections) {
+    ++N;
     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->Live) {
       S = nullptr;
       continue;
     }
 
-    StringRef OutsecName = getOutputSectionName(MS);
+    StringRef OutName = (PredictedOS.empty() || !PredictedOS[N - 1])
+                            ? getOutputSectionName(MS)
+                            : PredictedOS[N - 1]->Name;
     uint32_t Alignment = std::max<uint32_t>(MS->Alignment, MS->Entsize);
 
     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.
-      return Sec->Name == OutsecName && Sec->Flags == MS->Flags &&
-             Sec->Entsize == MS->Entsize && Sec->Alignment == Alignment;
+      //
+      // We are trying to predict the output section name and do not merge the
+      // sections which we think will be in the different outputs. This is a
+      // simplification that allows us do merging early before scanning the
+      // linker script commands.
+      return Sec->Flags == MS->Flags && Sec->Entsize == MS->Entsize &&
+             Sec->Alignment == Alignment &&
+             SecToOutputName.lookup(Sec) == OutName;
     });
     if (I == MergeSections.end()) {
       MergeSyntheticSection *Syn =
-          createMergeSynthetic(OutsecName, MS->Type, MS->Flags, Alignment);
+          createMergeSynthetic(MS->Name, MS->Type, MS->Flags, Alignment);
       MergeSections.push_back(Syn);
+      SecToOutputName.insert({Syn, OutName});
       I = std::prev(MergeSections.end());
       S = Syn;
       Syn->Entsize = MS->Entsize;
     } else {
       S = nullptr;
     }
     (*I)->addSection(MS);
   }

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

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+# RUN: echo "SECTIONS { \
+# RUN:   .rodata_foo : { *(.rodata.foo) } \
+# RUN:   .rodata_bar : { *(.rodata.bar) } \
+# RUN: }" > %t.script
+# RUN: ld.lld -o %t -script %t.script %t.o
+# RUN: llvm-readelf -S %t | FileCheck %s
+
+# CHECK:      [Nr] Name        Type     Address          Off    Size   ES Flg Lk Inf Al
+# CHECK-NEXT: [ 0]             NULL     0000000000000000 000000 000000 00     0  0   0
+# CHECK-NEXT: [ 1] .rodata_foo PROGBITS 0000000000000000 001000 000004 04  AM 0  0   4
+# CHECK-NEXT: [ 2] .rodata_bar PROGBITS 0000000000000004 001004 000004 04  AM 0  0   4
+
+.section .rodata.foo,"aM",@progbits,4
+.long 1
+
+.section .rodata.bar,"aM",@progbits,4
+.long 1

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 -t %t2 | FileCheck %s --check-prefix=GC
 
 # GC:        Name: .foo
 # GC-NEXT:   Type: SHT_NOBITS
 # GC-NEXT:   Flags [