Index: ELF/ICF.cpp
===================================================================
--- ELF/ICF.cpp
+++ ELF/ICF.cpp
@@ -275,10 +275,17 @@
 // 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)
+  if (!A || !B || A->NumRelocations != B->NumRelocations ||
+      A->Flags != B->Flags || A->getSize() != B->getSize() ||
+      A->Data != B->Data)
     return false;
 
+  const InputSection *LinkSecA = A->getLinkOrderSec();
+  const InputSection *LinkSecB = B->getLinkOrderSec();
+  if (LinkSecA || LinkSecB)
+    if (!equalsConstant(LinkSecA, LinkSecB))
+      return false;
+
   if (A->AreRelocsRela)
     return constantEq(A, A->template relas<ELFT>(), B,
                       B->template relas<ELFT>());
@@ -426,17 +433,10 @@
     for (size_t I = Begin + 1; I < End; ++I) {
       log("  removed " + Sections[I]->Name);
       Sections[Begin]->replace(Sections[I]);
+      if (InputSection *LinkOrder = Sections[I]->getLinkOrderSec())
+        log("  removed " + LinkOrder->Name);
     }
   });
-
-  // Mark ARM Exception Index table sections that refer to folded code
-  // sections as not live. These sections have an implict dependency
-  // via the link order dependency.
-  if (Config->EMachine == EM_ARM)
-    for (InputSectionBase *Sec : InputSections)
-      if (auto *S = dyn_cast<InputSection>(Sec))
-        if (S->Flags & SHF_LINK_ORDER)
-          S->Live = S->getLinkOrderDep()->Live;
 }
 
 // ICF entry point function.
Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -164,6 +164,7 @@
   }
 
   InputSection *getLinkOrderDep() const;
+  InputSection *getLinkOrderSec() const;
 
   void uncompress();
 
Index: ELF/InputSection.cpp
===================================================================
--- ELF/InputSection.cpp
+++ ELF/InputSection.cpp
@@ -241,6 +241,15 @@
   return nullptr;
 }
 
+InputSection *InputSectionBase::getLinkOrderSec() const {
+  std::vector<InputSection *> V;
+  for (InputSectionBase *S : DependentSections)
+    if (InputSection *Dep = S->getLinkOrderDep())
+      V.push_back(cast<InputSection>(S));
+  assert(V.size() <= 1);
+  return V.empty() ? nullptr : V[0];
+}
+
 // Returns a source location string. Used to construct an error message.
 template <class ELFT>
 std::string InputSectionBase::getLocation(uint64_t Offset) {
@@ -808,6 +817,11 @@
   this->Alignment = std::max(this->Alignment, Other->Alignment);
   Other->Repl = this->Repl;
   Other->Live = false;
+
+  // Handle SHF_LINK_ORDER sections. These sections have an
+  // implicit dependency via the link order dependency.
+  if (InputSection *LinkOrder = getLinkOrderSec())
+    LinkOrder->replace(Other->getLinkOrderSec());
 }
 
 template <class ELFT>
Index: test/ELF/icf-link-order.s
===================================================================
--- test/ELF/icf-link-order.s
+++ test/ELF/icf-link-order.s
@@ -0,0 +1,29 @@
+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --verbose | FileCheck %s
+# CHECK:      selected .text.foo
+# CHECK-NEXT:   removed .text.bar
+# CHECK-NEXT:   removed .order_bar
+# CHECK-NOT: selected
+# CHECK-NOT: removed
+
+.section .text.foo, "ax"
+nop
+
+.section .text.bar, "ax"
+nop
+
+.section .text.dah, "ax"
+nop
+
+.section .text.zed, "ax"
+nop
+
+.section .order_foo,"ao",@progbits,.text.foo
+.quad 0
+
+.section .order_bar,"ao",@progbits,.text.bar
+.quad 0
+
+.section .order_dah,"ao",@progbits,.text.dah
+.quad 1