[ELF] - Do not ICF two sections with different output sections when using linker scripts

[grimar]

Summary

This is https://bugs.llvm.org//show_bug.cgi?id=39418.

Currently, when LLD do ICF it checks if the output section name is the same,
but that works only for no linker script case.
We create output sections and assign input sections much later.
The patch adds logic to predict the output sections earlier, so that
we can ICF in a more correct way without complicated changes to linker design.

I used the test case provided on the PR page. Thanks, Andrew Ng :)

[ruiu]

I don't think this is necessarily a bug. At least, "predicating" the name of an output section does not seems a good idea to me. It is getting too tricky, and I don't like to add more complexity here. I generally do not encourage users use linker scripts as it makes linking slower and trickier, and it is to me an acceptable consequence that ICF folds input sections before linker scripts bin input sections to output sections.

[jhenderson]

In D54422#1296590, @ruiu wrote:

I don't think this is necessarily a bug. At least, "predicating" the name of an output section does not seems a good idea to me. It is getting too tricky, and I don't like to add more complexity here. I generally do not encourage users use linker scripts as it makes linking slower and trickier, and it is to me an acceptable consequence that ICF folds input sections before linker scripts bin input sections to output sections.

I agree that prediction seems like the wrong approach, unless we can guarantee 100% accuracy (prediction implies that it isn't always accurate). However, @ruiu, whilst you may not encourage users to use linker scripts, they are widely used, and in some instances, potentially even many, there is no reasonable alternative. ICF folding input sections between output sections can result in invalid output, especially if those output sections are supposed to be in different program segments, which could result in runtime crashes. I therefore would consider any such incorrect assignment a bug in LLD.

[peter.smith]

I agree with James here. I strongly suspect that in systems where merging content is a problem such as embedded systems with overlays or only a subset of memory available for booting there may be little correlation between the input section names chosen by the compiler and that given to the output section.

The only thing I can think of right now that doesn't involve an early assignment of input sections to output sections is to exploit the Repl field. When assigning InputSections to OutputSections then try and match the non-live sections against the InputSection Descriptions. If matches a different OutputSection to the InputSection it was folded into then mark it live and assign it to an OutputSection.

As an aside the approach outlined in https://llvm.org/devmtg/2017-10/slides/LTOLinkerScriptsEdlerVonKoch.pdf seems to favour an early assignment of InputSections to OutputSections I've not seen much movement on getting that upstream since the RFC at http://lists.llvm.org/pipermail/llvm-dev/2018-May/123252.html though.

[grimar]

Abandoning basing on comments (+another patch was posted instead).

ELF/ICF.cpp

 // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
 // in the Gold Linker
 // http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
 //
 //===----------------------------------------------------------------------===//
 
 #include "ICF.h"
 #include "Config.h"
+#include "LinkerScript.h"
+#include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Writer.h"
 #include "lld/Common/Threads.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Object/ELF.h"

 // except relocation targets.
 template <class ELFT>
 bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
   if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
       A->getSize() != B->getSize() || A->data() != B->data())
     return false;
 
   // If two sections have different output sections, we cannot merge them.
-  // FIXME: This doesn't do the right thing in the case where there is a linker
-  // script. We probably need to move output section assignment before ICF to
-  // get the correct behaviour here.
-  if (getOutputSectionName(A) != getOutputSectionName(B))
+  if (A->Parent != B->Parent ||
+      getOutputSectionName(A) != getOutputSectionName(B))
     return false;
 
   if (A->AreRelocsRela)
     return constantEq(A, A->template relas<ELFT>(), B,
                       B->template relas<ELFT>());
   return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
 }
 

 // The main function of ICF.
 template <class ELFT> void ICF<ELFT>::run() {
   // Collect sections to merge.
   for (InputSectionBase *Sec : InputSections)
     if (auto *S = dyn_cast<InputSection>(Sec))
       if (isEligible(S))
         Sections.push_back(S);
 
+  // When linker script is present, we do not want to perform ICF on
+  // sections that belong to the different output sections. Here we
+  // predict the output sections and store them as parents temporarily.
+  std::vector<OutputSection *> PredictedOS =
+      Script->predictOutputSections(Sections);
+  if (!PredictedOS.empty())
+    for (size_t I = 0; I < Sections.size(); ++I)
+      Sections[I]->Parent = PredictedOS[I];
+
   // Initially, we use hash values to partition sections.
   parallelForEach(Sections, [&](InputSection *S) {
     // Set MSB to 1 to avoid collisions with non-hash IDs.
     S->Class[0] = xxHash64(S->data()) | (1U << 31);
   });
 
   // From now on, sections in Sections vector are ordered so that sections
   // in the same equivalence class are consecutive in the vector.
for (size_t I = Begin + 1; I < End; ++I) {
 
       // At this point we know sections merged are fully identical and hence
       // we want to remove duplicate implicit dependencies such as link order
       // and relocation sections.
       for (InputSection *IS : Sections[I]->DependentSections)
         IS->Live = false;
     }
   });
+
+  // Set predicted temporarily parents back to zero.
+  if (!PredictedOS.empty())
+    for (InputSection *Sec : Sections)
+      Sec->Parent = nullptr;
 }
 
 // ICF entry point function.
 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
 
 template void elf::doIcf<ELF32LE>();
 template void elf::doIcf<ELF32BE>();
 template void elf::doIcf<ELF64LE>();
 template void elf::doIcf<ELF64BE>();

ELF/LinkerScript.h

class LinkerScript final {
   // LinkerScript.
   AddressState *Ctx = nullptr;
 
   OutputSection *Aether;
 
   uint64_t Dot;
 
 public:
+  std::vector<OutputSection *>
+  predictOutputSections(ArrayRef<InputSection *> 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;
+}
+
+// For the given list of input sections method returns the list of predicted
+// output sections. Method do only basic matching and allows us to prevent doing
+// ICF when output sections are predicted to be different. Returns an empty list
+// if linker script is not used.
+std::vector<OutputSection *>
+LinkerScript::predictOutputSections(ArrayRef<InputSection *> 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;
+
+        parallelForEachN(0, V.size(), [&](size_t I) {
+          if (!Ret[I] && matches(V[I]->Name, Cmd->SectionPatterns))
+            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();

test/ELF/linkerscript/icf-output-section.s

+# REQUIRES: x86
+
+# RUN: echo "SECTIONS { \
+# RUN:   .text.foo : { *(.text.foo) } .text.bar : { *(.text.bar) } \
+# RUN:   .rodata.foo : { *(.rodata.foo) } .rodata.bar : { *(.rodata.bar) } }" > %t.script
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+# RUN: ld.lld %t.o --script %t.script -o %t --icf=all --ignore-data-address-equality --print-icf-sections | count 0
+
+.global _start
+.type _start,@function
+_start:
+ nop
+
+.global foo_func
+.type foo_func,@function
+.section .text.foo,"ax",@progbits
+foo_func:
+ ret
+
+.global bar_func
+.type bar_func,@function
+.section .text.bar,"ax",@progbits
+bar_func:
+ ret
+
+.global foo_data
+.type foo_data,@object
+.section .rodata.foo,"a",@progbits
+foo_data:
+.long 42
+
+.global bar_data
+.type bar_data,@object
+.section .rodata.bar,"a",@progbits
+bar_data:
+.long 42