[lld][ELF] remove empty SyntheticSections from inputSections

[amilendra]

Summary

Change removeUnusedSyntheticSections() to actually remove empty
SyntheticSections in inputSections.

In addition to doing what removeUnusedSyntheticSections() was meant
to do, this will also make the shuffle-sections tests, which shuffles
inputSections, less sensitive to empty Synthetic Sections that
will not appear in the final image.

[MaskRay]

lld/ELF/Writer.cpp

1896

Use isa

1901

Delete. The code below can handle the case.

1920

The right hand side of auto end is now complex.

While here, you can refactor the code to do one batch llvm::erase_if for isd->sections instead of N llvm::erase_if.

You may need a DenseSet

[amilendra]

Address review comments

• Use isa instead of dyncast.
• Delete unnecessary check for vector end.
• Refactor erasing of unused synthetic sections from corresponding input section descriptions

[amilendra]

lld/ELF/Writer.cpp

1920

I hope this is what you had in mind.

[amilendra]

Rebase

[amilendra]

Rebase attempt 2

[amilendra]

Fix clang-tidy errors

[amilendra]

[lld][ELF] remove empty SyntheticSections from inputSections

The clang-tidy warnings I got locally were different from upstream.
Fix upstream warnings only.

lld/ELF/Writer.cpp

 // don't need a .got (for example) at all because there's no
 // relocation that needs a .got, we don't want to emit .got.
 //
 // To deal with the above problem, this function is called after
 // scanRelocations is called to remove synthetic sections that turn
 // out to be empty.
 static void removeUnusedSyntheticSections() {
   // All input synthetic sections that can be empty are placed after
-  // all regular ones. We iterate over them all and exit at first
-  // non-synthetic.
-  for (InputSectionBase *s : llvm::reverse(inputSections)) {
-    SyntheticSection *ss = dyn_cast<SyntheticSection>(s);
-    if (!ss)
-      return;
-    OutputSection *os = ss->getParent();
-    if (!os || ss->isNeeded())
-      continue;
+  // all regular ones. Reverse iterate to find the first synthetic section
+  // after a non-synthetic one which will be our starting point.
+  auto Start = std::find_if(inputSections.rbegin(), inputSections.rend(),
+                            [](InputSectionBase *S) {
+                              return !isa<SyntheticSection>(S);
+                            })
+                   .base();
+
+  DenseSet<InputSectionDescription *> IsdSet;
+  // Mark unused synthetic sections for deletion
+  auto End = std::stable_partition(
+      Start, inputSections.end(), [&](InputSectionBase *S) {
+        SyntheticSection *Ss = dyn_cast<SyntheticSection>(S);
+        OutputSection *Os = Ss->getParent();
+        if (!Os || Ss->isNeeded())
+          return true;
 
-    // If we reach here, then ss is an unused synthetic section and we want to
-    // remove it from the corresponding input section description, and
+        // If we reach here, then Ss is an unused synthetic section and we want
+        // to remove it from the corresponding input section description, and
         // orphanSections.
-    for (BaseCommand *b : os->sectionCommands)
-      if (auto *isd = dyn_cast<InputSectionDescription>(b))
-        llvm::erase_if(isd->sections,
-                       [=](InputSection *isec) { return isec == ss; });
-    llvm::erase_if(script->orphanSections,
-                   [=](const InputSectionBase *isec) { return isec == ss; });
-  }
+        for (BaseCommand *B : Os->sectionCommands)
+          if (auto *Isd = dyn_cast<InputSectionDescription>(B))
+            IsdSet.insert(Isd);
+
+        llvm::erase_if(
+            script->orphanSections,
+            [=](const InputSectionBase *Isec) { return Isec == Ss; });
+
+        return false;
+      });
+
+  DenseSet<InputSectionBase *> Unused(End, inputSections.end());
+  for (auto *Isd : IsdSet)
+    llvm::erase_if(Isd->sections,
+                   [=](InputSection *Isec) { return Unused.count(Isec); });
+
+  // Erase unused synthetic sections.
+  inputSections.erase(End, inputSections.end());
 }
 
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::finalizeSections() {
   Out::preinitArray = findSection(".preinit_array");
   Out::initArray = findSection(".init_array");
   Out::finiArray = findSection(".fini_array");
 

lld/test/ELF/shuffle-sections-init-fini.s

 
 # CHECK:      Hex dump of section '.fini'
 # CHECK-NEXT: 00010203 04050607 08090a0b
 
 ## SHT_INIT_ARRAY/SHT_FINI_ARRAY with explicit priorities are still ordered.
 # CHECK:      Hex dump of section '.init_array'
 # CHECK-NEXT: 0x{{[0-9a-f]+}} ff
 # ORDERED-SAME: 000102 03040506 0708090a 0b
-# SHUFFLED-SAME: 080301 04050907 0b020a06 00
+# SHUFFLED-SAME: 070201 0006090a 040b0503 08
 
 # CHECK:      Hex dump of section '.fini_array'
 # CHECK-NEXT: 0x{{[0-9a-f]+}} ff
 # ORDERED-SAME:  000102 03040506 0708090a 0b
-# SHUFFLED-SAME: 0a0405 08070b02 03090006 01
+# SHUFFLED-SAME: 070008 0a040209 03010b06 05
 
 ## With a SECTIONS command, SHT_INIT_ARRAY prirotities are ignored.
 ## All .init_array* are shuffled together.
 # RUN: echo 'SECTIONS { \
 # RUN:   .init_array : { *(.init_array*) } \
 # RUN:   .fini_array : { *(.fini_array*) }}' > %t.script
 # RUN: ld.lld -T %t.script %t.o -o %t2
 # RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t2 | \
 # RUN:   FileCheck --check-prefixes=CHECK2,ORDERED2 %s
 # RUN: ld.lld -T %t.script %t.o --shuffle-sections '*=1' -o %t3
 # RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t3 | \
 # RUN:   FileCheck --check-prefixes=CHECK2,SHUFFLED2 %s
 
 # CHECK2:       Hex dump of section '.init_array'
 # ORDERED2-NEXT:  0x{{[0-9a-f]+}} 00010203 04050607 08090a0b ff
-# SHUFFLED2-NEXT: 0x{{[0-9a-f]+}} 08030104 0509070b 02ff0a06 00
+# SHUFFLED2-NEXT: 0x{{[0-9a-f]+}} 07020100 06090a04 0b050308 ff
 
 .irp i,0,1,2,3,4,5,6,7,8,9,10,11
   .section .init,"ax",@progbits,unique,\i
   .byte \i
   .section .fini,"ax",@progbits,unique,\i
   .byte \i
   .section .init_array,"aw",@init_array,unique,\i
   .byte \i
   .section .fini_array,"aw",@fini_array,unique,\i
   .byte \i
 .endr
 
 .section .init_array.1,"aw",@init_array
 .byte 255
 .section .fini_array.1,"aw",@fini_array
 .byte 255

lld/test/ELF/shuffle-sections.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 
 # RUN: ld.lld %t.o -o %t.out
 # RUN: llvm-readelf -x .text %t.out | FileCheck %s
 # CHECK: Hex dump of section '.text':
 # CHECK-NEXT: 01020304
 
 ## --shuffle-sections= shuffles input sections.
 # RUN: ld.lld --shuffle-sections='*=1' %t.o -o %t1.out
 # RUN: llvm-readelf -x .text %t1.out | FileCheck %s --check-prefix=SHUFFLE1
 # SHUFFLE1: Hex dump of section '.text':
-# SHUFFLE1-NEXT: 0203cccc 0104
+# SHUFFLE1-NEXT: 01020403
 
 ## Test that --shuffle-sections= can be used with --symbol-ordering-file
 # RUN: echo "foo" > %t_order.txt
 # RUN: echo "_start " >> %t_order.txt
 
 # RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections='*=2' %t.o -o %t2.out
 # RUN: llvm-readelf -x .text %t2.out | FileCheck %s --check-prefix=SHUFFLE2
 # SHUFFLE2: Hex dump of section '.text':
-# SHUFFLE2-NEXT: 02cccccc 010403
+# SHUFFLE2-NEXT: 02cccccc 010304
 
 # RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections='*=3' %t.o -o %t3.out
 # RUN: llvm-readelf -x .text %t3.out | FileCheck %s --check-prefix=SHUFFLE3
 # SHUFFLE3: Hex dump of section '.text':
 # SHUFFLE3-NEXT: 02cccccc 010403
 
 ## As a special case, -1 reverses sections as a stable transform.
 # RUN: ld.lld --shuffle-sections '*=-1' %t.o -o %t-1.out