[ELF] Do not ICF two sections with different output sections when there is a linker script

[MaskRay]

Summary

This complements D47241 for the non-linker-script (getOutputSectionName) case.

This implements the unfold approach as briefed at https://reviews.llvm.org/D54422#1302994

// Do not ICF fold input sections between output sections. If the output
// sections of sec and the InputSection it gets folded into are different,
// unfold it. sec->repl may have increased alignment or be have moved to the
// main partition, but that does not matter.

--print-icf-sections is not handled.

[MaskRay]

D66717 should be better

[MaskRay]

For the test case linkerscript/icf-different-output-sections.s added in D66717

% ld.lld a.o -T a.x --icf=all --print-icf-sections       
## need more code to make the log messages correct
selected section a.o:(.rodata.foo0)
  removing identical section a.o:(.rodata.foo1)
  removing identical section a.o:(.rodata.bar0) # this will be unfolded
  removing identical section a.o:(.rodata.bar1) # this will be unfolded
selected section a.o:(.text.foo0)
  removing identical section a.o:(.text.foo1)
  removing identical section a.o:(.text.bar0) # this will be unfolded
  removing identical section a.o:(.text.bar1) # this will be unfolded

             VMA              LMA     Size Align Out     In      Symbol
               0                0        1     1 .rodata.foo
               0                0        1     1         a.o:(.rodata.foo0)
               1                1        2     1 .rodata.bar
               1                1        1     1         a.o:(.rodata.bar0)
               2                2        1     1         a.o:(.rodata.bar1) # this was folded into .rodata.foo0, then unfolded, but it can be folded into .rodata.bar0 again
               3                3        1     1 .text.foo
               3                3        1     1         a.o:(.text.foo0)
               4                4        2     1 .text.bar
               4                4        1     1         a.o:(.text.bar0)
               5                5        1     1         a.o:(.text.bar1) # ditto

[grimar]

D66717 should be better

I still need to look at D66717 closer, but I agree, I think this one is not a right approach probably.

Making sections dead and folding them, but then ressurrecting and unfolding looks
tricky: I do not think we have any other place where we set Live bit to
a dead input section (though we can do it for output section in adjustSectionsBeforeSorting).
Doing this seems breaks this part of LLD design and my impression is that we should avoid doing it.

ELF/ICF.cpp

 // Compare "non-moving" part of two InputSections, namely everything
 // 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 two sections have different output sections, we cannot merge them. When
+  // there is a linker script, getOutputSectionName may be inaccurate, sections
+  // going into different output sections may get folded but they will be
+  // unfolded in LinkerScript::processSectionCommands.
   if (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>());
 }

ELF/LinkerScript.cpp

 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();
 
     for (InputSectionBase *sec : inputSections) {
-      if (!sec->isLive() || sec->assigned)
+      if (sec->assigned || (!sec->isLive() && sec->repl == sec))
         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.
       //
for (InputSection *s : v) {
     // 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->assigned = false;
+    // Entirely discarded. s->repl != s indicates a section that can be unfolded
+    // later.
     s->markDead();
+    s->repl = s;
+
     discard(s->dependentSections);
   }
 }
 
 std::vector<InputSection *>
 LinkerScript::createInputSectionList(OutputSection &outCmd) {
   std::vector<InputSection *> ret;
 
if (auto *sec = dyn_cast<OutputSection>(base)) {
 
       sec->sectionIndex = i++;
       if (sec->noload)
         sec->type = SHT_NOBITS;
       if (sec->nonAlloc)
         sec->flags &= ~(uint64_t)SHF_ALLOC;
     }
   }
+
+  for (BaseCommand *base : script->sectionCommands)
+    if (auto *sec = dyn_cast<OutputSection>(base))
+      for (BaseCommand *sub_base : sec->sectionCommands)
+        if (auto *isd = dyn_cast<InputSectionDescription>(sub_base)) {
+          // Do not ICF fold input sections between output sections. If the
+          // output sections of sec and the InputSection it gets folded into are
+          // different, unfold it. sec->repl may have increased alignment or be
+          // have moved to the main partition, but that does not matter.
+          for (InputSection *s : isd->sections)
+            if (s->repl != s &&
+                cast<InputSection>(s->repl)->getParent() != s->getParent()) {
+              s->repl = s;
+              s->markLive();
+              for (InputSection *dependent : s->dependentSections)
+                dependent->markLive();
+            }
+
+          llvm::erase_if(isd->sections,
+                         [](InputSection *isec) { return !isec->isLive(); });
+        }
+
   ctx = nullptr;
 }
 
 static OutputSection *findByName(ArrayRef<BaseCommand *> vec,
                                  StringRef name) {
   for (BaseCommand *base : vec)
     if (auto *sec = dyn_cast<OutputSection>(base))
       if (sec->name == name)