diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
--- a/lld/ELF/InputSection.cpp
+++ b/lld/ELF/InputSection.cpp
@@ -1326,6 +1326,18 @@
 
 template <class ELFT, class RelTy>
 void EhInputSection::split(ArrayRef<RelTy> rels) {
+  // getReloc expects the relocations to be sorted by r_offset. See the comment
+  // in scanRelocs.
+  SmallVector<RelTy, 0> sorted;
+  auto cmp = [](const RelTy &a, const RelTy &b) {
+    return a.r_offset < b.r_offset;
+  };
+  if (!llvm::is_sorted(rels, cmp)) {
+    sorted.assign(rels.begin(), rels.end());
+    llvm::stable_sort(sorted, cmp);
+    rels = sorted;
+  }
+
   unsigned relI = 0;
   for (size_t off = 0, end = data().size(); off != end;) {
     size_t size = readEhRecordSize(this, off);
diff --git a/lld/ELF/Relocations.cpp b/lld/ELF/Relocations.cpp
--- a/lld/ELF/Relocations.cpp
+++ b/lld/ELF/Relocations.cpp
@@ -1576,6 +1576,22 @@
   if (config->emachine == EM_PPC64)
     checkPPC64TLSRelax<RelTy>(sec, rels);
 
+  // For EhInputSection, OffsetGetter expects the relocations to be sorted by
+  // r_offset. In rare cases (.eh_frame pieces are reordered by a linker
+  // script), the relocations may be unordered. Allocate a temporary vector and
+  // sort the relocations.
+  SmallVector<RelTy, 0> sorted;
+  if (isa<EhInputSection>(sec)) {
+    auto cmp = [](const RelTy &a, const RelTy &b) {
+      return a.r_offset < b.r_offset;
+    };
+    if (!llvm::is_sorted(rels, cmp)) {
+      sorted.assign(rels.begin(), rels.end());
+      llvm::stable_sort(sorted, cmp);
+      rels = sorted;
+    }
+  }
+
   for (auto i = rels.begin(), end = rels.end(); i != end;)
     scanReloc<ELFT>(sec, getOffset, i, rels.begin(), end);
 
diff --git a/lld/test/ELF/eh-frame-unordered-r_offset.s b/lld/test/ELF/eh-frame-unordered-r_offset.s
new file mode 100644
--- /dev/null
+++ b/lld/test/ELF/eh-frame-unordered-r_offset.s
@@ -0,0 +1,30 @@
+# REQUIRES: x86
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/a.s -o %t/a.o
+# RUN: cp %t/a.o %t/b.o
+# RUN: ld.lld -r -T %t/lds %t/a.o %t/b.o -o %t/c.o
+# RUN: llvm-readelf -r %t/c.o | FileCheck %s --check-prefix=REL
+
+## If we swap two input .eh_frame, the r_offset values in relocations will be
+## unordered.
+# REL:          Offset
+# REL-NEXT: 0000000000000050
+# REL-NEXT: 0000000000000020
+
+## Test we can handle the rare case.
+# RUN: ld.lld %t/c.o -o %t/c
+# RUN: llvm-dwarfdump --eh-frame %t/c | FileCheck %s
+
+# CHECK: 00000000 00000014 00000000 CIE
+# CHECK: 00000018 00000014 0000001c FDE cie=00000000
+# CHECK: 00000030 00000014 00000034 FDE cie=00000000
+
+#--- a.s
+.cfi_startproc
+nop
+.cfi_endproc
+
+#--- lds
+SECTIONS {
+  .eh_frame : { *b.o(.eh_frame) *a.o(.eh_frame) }
+}