[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

 // 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. 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 !dyn_cast<SyntheticSection>(s);
+                              return !isa<SyntheticSection>(s);
                             })
                    .base();
 
-  // All inputSections are regular ones. Nothing to do.
-  if (start == inputSections.end())
-    return;
-
+  DenseSet<InputSectionDescription *> isdSet;
   // Mark unused synthetic sections for deletion
-  auto end =
-      std::remove_if(start, inputSections.end(), [](InputSectionBase *s) {
+  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 false;
+          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
         // orphanSections.
         for (BaseCommand *b : os->sectionCommands)
           if (auto *isd = dyn_cast<InputSectionDescription>(b))
-            llvm::erase_if(isd->sections,
-                           [=](InputSection *isec) { return isec == ss; });
+            isdSet.insert(isd);
+
         llvm::erase_if(
             script->orphanSections,
             [=](const InputSectionBase *isec) { return isec == ss; });
-        return true;
+
+        return false;
       });
 
-  // Erase unused synthetic section.
+  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");