Index: ELF/OutputSections.cpp
===================================================================
--- ELF/OutputSections.cpp
+++ ELF/OutputSections.cpp
@@ -941,7 +941,8 @@
   auto RelI = Rels.begin();
   auto RelE = Rels.end();
 
-  DenseMap<unsigned, unsigned> OffsetToIndex;
+  // Maps offset to Index/Length pair.
+  DenseMap<unsigned, std::pair<unsigned, uint32_t>> OffsetToData;
   while (!D.empty()) {
     if (D.size() < 4)
       error("Truncated CIE/FDE length");
@@ -974,21 +975,23 @@
 
       std::pair<StringRef, StringRef> CieInfo(Entry, Personality);
       auto P = CieMap.insert(std::make_pair(CieInfo, Cies.size()));
-      if (P.second) {
+      if (P.second)
         Cies.push_back(C);
-        this->Header.sh_size += Length;
-      }
-      OffsetToIndex[Offset] = P.first->second;
+      OffsetToData[Offset] = std::make_pair(P.first->second, Length);
     } else {
       if (!HasReloc)
         error("FDE doesn't reference another section");
       InputSectionBase<ELFT> *Target = S->getRelocTarget(*RelI);
       if (Target != &InputSection<ELFT>::Discarded && Target->isLive()) {
         uint32_t CieOffset = Offset + 4 - ID;
-        auto I = OffsetToIndex.find(CieOffset);
-        if (I == OffsetToIndex.end())
+        auto I = OffsetToData.find(CieOffset);
+        if (I == OffsetToData.end())
           error("Invalid CIE reference");
-        Cies[I->second].Fdes.push_back(EHRegion<ELFT>(S, Index));
+        std::pair<unsigned, uint32_t> &IndLen = I->second;
+        Cie<ELFT> &Cie = Cies[IndLen.first];
+        if (Cie.Fdes.empty())
+          this->Header.sh_size += IndLen.second;
+        Cie.Fdes.push_back(EHRegion<ELFT>(S, Index));
         this->Header.sh_size += Length;
       }
     }
@@ -1014,6 +1017,9 @@
   const endianness E = ELFT::TargetEndianness;
   size_t Offset = 0;
   for (const Cie<ELFT> &C : Cies) {
+    if (C.Fdes.empty())
+      continue;
+
     size_t CieOffset = Offset;
 
     StringRef CieData = C.data();
Index: test/ELF/eh-frame-opt.s
===================================================================
--- test/ELF/eh-frame-opt.s
+++ test/ELF/eh-frame-opt.s
@@ -0,0 +1,39 @@
+// REQUIRES: x86
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+// RUN: ld.lld --gc-sections %t.o -o %t
+// RUN: llvm-readobj -s -section-data %t | FileCheck %s
+
+// Here we check that if all FDEs referencing a CIE
+// were removed, CIE is also removed.
+// CHECK:        Section {
+// CHECK:        Index:
+// CHECK:        Name: .eh_frame
+// CHECK-NEXT:   Type: SHT_X86_64_UNWIND
+// CHECK-NEXT:   Flags [
+// CHECK-NEXT:     SHF_ALLOC
+// CHECK-NEXT:   ]
+// CHECK-NEXT:   Address: 0x10120
+// CHECK-NEXT:   Offset: 0x120
+// CHECK-NEXT:   Size: 0
+// CHECK-NEXT:   Link: 0
+// CHECK-NEXT:   Info: 0
+// CHECK-NEXT:   AddressAlignment: 8
+// CHECK-NEXT:   EntrySize: 0
+// CHECK-NEXT:   SectionData (
+// CHECK-NEXT:   )
+// CHECK-NEXT: }
+
+.section foo,"ax",@progbits
+.cfi_startproc
+ nop
+.cfi_endproc
+
+.section bar,"ax",@progbits
+.cfi_startproc
+ nop
+ nop
+.cfi_endproc
+
+.text
+.globl _start;
+_start: