diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -1893,36 +1893,39 @@
   // 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());
 }