diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h
--- a/lld/ELF/InputSection.h
+++ b/lld/ELF/InputSection.h
@@ -9,6 +9,7 @@
 #ifndef LLD_ELF_INPUT_SECTION_H
 #define LLD_ELF_INPUT_SECTION_H
 
+#include "Config.h"
 #include "Relocations.h"
 #include "lld/Common/CommonLinkerContext.h"
 #include "lld/Common/LLVM.h"
@@ -315,7 +316,8 @@
 struct EhSectionPiece {
   EhSectionPiece(size_t off, InputSectionBase *sec, uint32_t size,
                  unsigned firstRelocation)
-      : inputOff(off), sec(sec), size(size), firstRelocation(firstRelocation) {}
+      : inputOff(off), sec(sec), size(size), live(!config->gcSections),
+        firstRelocation(firstRelocation) {}
 
   ArrayRef<uint8_t> data() const {
     return {sec->content().data() + this->inputOff, size};
@@ -324,7 +326,8 @@
   size_t inputOff;
   ssize_t outputOff = -1;
   InputSectionBase *sec;
-  uint32_t size;
+  uint32_t size : 31;
+  uint32_t live : 1;
   unsigned firstRelocation;
 };
 
diff --git a/lld/ELF/MarkLive.cpp b/lld/ELF/MarkLive.cpp
--- a/lld/ELF/MarkLive.cpp
+++ b/lld/ELF/MarkLive.cpp
@@ -48,6 +48,11 @@
 
   void run();
   void moveToMain();
+  // Scan .eh_frame sections and mark live FDEs and CIEs as well as all other
+  // sections referenced by them. This helps collecting sections which are
+  // referenced only by dead FDEs/CIEs.
+  // This should be called for the main partition, after processing all parts.
+  void processEhFrameSections();
 
 private:
   void enqueue(InputSectionBase *sec, uint64_t offset);
@@ -60,6 +65,14 @@
   template <class RelTy>
   void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels);
 
+  template <class RelTy>
+  void scanFde(EhInputSection &EH, ArrayRef<RelTy> Rels,
+               const EhSectionPiece &Fde);
+
+  template <class RelTy>
+  void scanCie(EhInputSection &EH, ArrayRef<RelTy> Rels,
+               const EhSectionPiece &Cie);
+
   // The index of the partition that we are currently processing.
   unsigned partition;
 
@@ -72,6 +85,30 @@
 };
 } // namespace
 
+// Return a CIE referenced by a given FDE or nullptr if CIE could not be found.
+template <class ELFT>
+static EhSectionPiece *getCieForFde(const EhSectionPiece &fde,
+                                    SmallVectorImpl<EhSectionPiece> &cies) {
+  if (cies.empty())
+    return nullptr;
+
+  const uint32_t id = read32<ELFT::TargetEndianness>(fde.data().data() + 4);
+  uint32_t cieOffset = fde.inputOff + 4 - id;
+
+  // In most cases, an FDE refers to the most recent CIE.
+  if (cies.back().inputOff == cieOffset)
+    return &cies.back();
+
+  auto it = llvm::lower_bound(cies, cieOffset,
+                              [](EhSectionPiece &cie, uint32_t offset) {
+                                return cie.inputOff < offset;
+                              });
+  if (it != cies.end() && (*it).inputOff == cieOffset)
+    return &*it;
+
+  return nullptr;
+}
+
 template <class ELFT>
 static uint64_t getAddend(InputSectionBase &sec,
                           const typename ELFT::Rel &rel) {
@@ -130,33 +167,60 @@
 // * CIEs can refer to a personality function.
 // * FDEs can refer to a LSDA
 // * FDEs refer to the function they contain information about
-// The last kind of relocation cannot keep the referred section alive, or they
-// would keep everything alive in a common object file. In fact, each FDE is
-// alive if the section it refers to is alive.
-// To keep things simple, in here we just ignore the last relocation kind. The
-// other two keep the referred section alive.
-//
-// A possible improvement would be to fully process .eh_frame in the middle of
-// the gc pass. With that we would be able to also gc some sections holding
-// LSDAs and personality functions if we found that they were unused.
+// The last kind of relocation is used to keep a FDE alive if the section
+// it refers to is alive. In that case, everything which is referenced from
+// that FDE should be marked, including a LSDA, a CIE and a personality
+// function. These sections might reference to other sections, so they
+// are added to the GC queue.
 template <class ELFT>
 template <class RelTy>
 void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &eh,
                                         ArrayRef<RelTy> rels) {
-  for (const EhSectionPiece &cie : eh.cies)
-    if (cie.firstRelocation != unsigned(-1))
-      resolveReloc(eh, rels[cie.firstRelocation], false);
-  for (const EhSectionPiece &fde : eh.fdes) {
-    size_t firstRelI = fde.firstRelocation;
-    if (firstRelI == (unsigned)-1)
+  for (EhSectionPiece &fde : eh.fdes) {
+    if (fde.live // This FDE is already fully processed.
+        || !elf::isFdeLive<ELFT>(fde, rels))
+      continue;
+    fde.live = true;
+    scanFde(eh, rels, fde);
+
+    // Find the corresponding CIE.
+    EhSectionPiece *cie = getCieForFde<ELFT>(fde, eh.cies);
+    if (!cie)
+      fatal(toString(&eh) + ": invalid CIE reference");
+    if (cie->live) // Already processed.
       continue;
-    uint64_t pieceEnd = fde.inputOff + fde.size;
-    for (size_t j = firstRelI, end2 = rels.size();
-         j < end2 && rels[j].r_offset < pieceEnd; ++j)
-      resolveReloc(eh, rels[j], true);
+    cie->live = true;
+    scanCie(eh, rels, *cie);
   }
 }
 
+template <class ELFT>
+template <class RelTy>
+void MarkLive<ELFT>::scanFde(EhInputSection &eh, ArrayRef<RelTy> rels,
+                             const EhSectionPiece &fde) {
+  uint64_t fdeEnd = fde.inputOff + fde.size;
+  // The first relocation is known to point to the described function,
+  // so it is safe to skip it when looking for LSDAs.
+  for (unsigned i = fde.firstRelocation + 1, end = rels.size();
+       i < end && rels[i].r_offset < fdeEnd; ++i)
+    // In an FDE, the relocations point to the described function or to a LSDA.
+    // The described function is already marked and calling Fn for it is safe.
+    // Although the main intent here is to mark LSDAs, we do not need to
+    // recognize them especially and can process all references the same way.
+    resolveReloc(eh, rels[i], true);
+}
+
+template <class ELFT>
+template <class RelTy>
+void MarkLive<ELFT>::scanCie(EhInputSection &eh, ArrayRef<RelTy> rels,
+                             const EhSectionPiece &cie) {
+  if (cie.firstRelocation == (unsigned)-1)
+    return;
+  // In a CIE, we only need to worry about the first relocation.
+  // It is known to point to the personality function.
+  resolveReloc(eh, rels[cie.firstRelocation], false);
+}
+
 // Some sections are used directly by the loader, so they should never be
 // garbage-collected. This function returns true if a given section is such
 // section.
@@ -231,17 +295,6 @@
   for (StringRef s : script->referencedSymbols)
     markSymbol(symtab.find(s));
 
-  // Mark .eh_frame sections as live because there are usually no relocations
-  // that point to .eh_frames. Otherwise, the garbage collector would drop
-  // all of them. We also want to preserve personality routines and LSDA
-  // referenced by .eh_frame sections, so we scan them for that here.
-  for (EhInputSection *eh : ctx.ehInputSections) {
-    const RelsOrRelas<ELFT> rels = eh->template relsOrRelas<ELFT>();
-    if (rels.areRelocsRel())
-      scanEhFrameSection(*eh, rels.rels);
-    else if (rels.relas.size())
-      scanEhFrameSection(*eh, rels.relas);
-  }
   for (InputSectionBase *sec : ctx.inputSections) {
     if (sec->flags & SHF_GNU_RETAIN) {
       enqueue(sec, 0);
@@ -298,6 +351,23 @@
   mark();
 }
 
+template <class ELFT> void MarkLive<ELFT>::processEhFrameSections() {
+  for (;;) {
+    for (EhInputSection *eh : ctx.ehInputSections) {
+      assert(eh->isLive() &&
+             "The section is expected to be marked in MarkLive<ELFT>::run()");
+      const RelsOrRelas<ELFT> rels = eh->template relsOrRelas<ELFT>();
+      if (rels.areRelocsRel())
+        scanEhFrameSection(*eh, rels.rels);
+      else if (rels.relas.size())
+        scanEhFrameSection(*eh, rels.relas);
+    }
+    if (queue.empty())
+      return;
+    mark();
+  }
+}
+
 template <class ELFT> void MarkLive<ELFT>::mark() {
   // Mark all reachable sections.
   while (!queue.empty()) {
@@ -374,6 +444,8 @@
   if (partitions.size() != 1)
     MarkLive<ELFT>(1).moveToMain();
 
+  MarkLive<ELFT>(1).processEhFrameSections();
+
   // Report garbage-collected sections.
   if (config->printGcSections)
     for (InputSectionBase *sec : ctx.inputSections)
diff --git a/lld/ELF/SyntheticSections.h b/lld/ELF/SyntheticSections.h
--- a/lld/ELF/SyntheticSections.h
+++ b/lld/ELF/SyntheticSections.h
@@ -1233,6 +1233,9 @@
 
 void addVerneed(Symbol *ss);
 
+template <class ELFT, class RelTy>
+Defined *isFdeLive(EhSectionPiece &fde, ArrayRef<RelTy> rels);
+
 // Linker generated per-partition sections.
 struct Partition {
   StringRef name;
diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -373,10 +373,8 @@
   return rec;
 }
 
-// There is one FDE per function. Returns a non-null pointer to the function
-// symbol if the given FDE points to a live function.
 template <class ELFT, class RelTy>
-Defined *EhFrameSection::isFdeLive(EhSectionPiece &fde, ArrayRef<RelTy> rels) {
+Defined *elf::isFdeLive(EhSectionPiece &fde, ArrayRef<RelTy> rels) {
   auto *sec = cast<EhInputSection>(fde.sec);
   unsigned firstRelI = fde.firstRelocation;
 
@@ -390,11 +388,20 @@
 
   const RelTy &rel = rels[firstRelI];
   Symbol &b = sec->template getFile<ELFT>()->getRelocTargetSym(rel);
-
-  // FDEs for garbage-collected or merged-by-ICF sections, or sections in
-  // another partition, are dead.
   if (auto *d = dyn_cast<Defined>(&b))
-    if (!d->folded && d->section && d->section->partition == partition)
+    // FDEs for garbage-collected or merged-by-ICF sections are dead.
+    if (!d->folded && d->section && d->section->partition)
+      return d;
+  return nullptr;
+}
+
+// There is one FDE per function. Returns a non-null pointer to the function
+// symbol if the given FDE points to a live function.
+template <class ELFT, class RelTy>
+Defined *EhFrameSection::isFdeLive(EhSectionPiece &fde, ArrayRef<RelTy> rels) {
+  if (auto *d = elf::isFdeLive<ELFT>(fde, rels))
+    // FDEs for sections in another partition are dead.
+    if (d->section->partition == partition)
       return d;
   return nullptr;
 }
@@ -406,9 +413,14 @@
 template <class ELFT, class RelTy>
 void EhFrameSection::addRecords(EhInputSection *sec, ArrayRef<RelTy> rels) {
   offsetToCie.clear();
-  for (EhSectionPiece &cie : sec->cies)
+  for (EhSectionPiece &cie : sec->cies) {
+    if (!cie.live)
+      continue;
     offsetToCie[cie.inputOff] = addCie<ELFT>(cie, rels);
+  }
   for (EhSectionPiece &fde : sec->fdes) {
+    if (!fde.live)
+      continue;
     uint32_t id = endian::read32<ELFT::TargetEndianness>(fde.data().data() + 4);
     CieRecord *rec = offsetToCie[fde.inputOff + 4 - id];
     if (!rec)
@@ -3965,3 +3977,20 @@
 template class elf::PartitionProgramHeadersSection<ELF32BE>;
 template class elf::PartitionProgramHeadersSection<ELF64LE>;
 template class elf::PartitionProgramHeadersSection<ELF64BE>;
+
+template Defined *elf::isFdeLive<ELF32LE, typename ELF32LE::Rel>(
+    EhSectionPiece &fde, ArrayRef<typename ELF32LE::Rel> rels);
+template Defined *elf::isFdeLive<ELF32LE, typename ELF32LE::Rela>(
+    EhSectionPiece &fde, ArrayRef<typename ELF32LE::Rela> rels);
+template Defined *elf::isFdeLive<ELF64LE, typename ELF64LE::Rel>(
+    EhSectionPiece &fde, ArrayRef<typename ELF64LE::Rel> rels);
+template Defined *elf::isFdeLive<ELF64LE, typename ELF64LE::Rela>(
+    EhSectionPiece &fde, ArrayRef<typename ELF64LE::Rela> rels);
+template Defined *elf::isFdeLive<ELF32BE, typename ELF32BE::Rel>(
+    EhSectionPiece &fde, ArrayRef<typename ELF32BE::Rel> rels);
+template Defined *elf::isFdeLive<ELF32BE, typename ELF32BE::Rela>(
+    EhSectionPiece &fde, ArrayRef<typename ELF32BE::Rela> rels);
+template Defined *elf::isFdeLive<ELF64BE, typename ELF64BE::Rel>(
+    EhSectionPiece &fde, ArrayRef<typename ELF64BE::Rel> rels);
+template Defined *elf::isFdeLive<ELF64BE, typename ELF64BE::Rela>(
+    EhSectionPiece &fde, ArrayRef<typename ELF64BE::Rela> rels);
diff --git a/lld/test/ELF/eh-frame-gc3.s b/lld/test/ELF/eh-frame-gc3.s
new file mode 100644
--- /dev/null
+++ b/lld/test/ELF/eh-frame-gc3.s
@@ -0,0 +1,37 @@
+// This checks that Personality Routine and LSDA are removed when functions
+// which use them get collected.
+
+// REQUIRES: x86
+// RUN: llvm-mc -filetype=obj -triple=i686-pc-linux %s -o %t.o
+// RUN: ld.lld %t.o --gc-sections -o %tout
+// RUN: llvm-nm %tout | FileCheck %s
+
+// CHECK:     _start
+// CHECK-NOT: foo
+// CHECK-NOT: lsda
+// CHECK-NOT: personality
+
+        .global _start, foo, lsda, personality
+        .text
+_start:
+        .cfi_startproc
+        nop
+        .cfi_endproc
+
+        .section ".text.foo","ax"
+foo:
+        .cfi_startproc
+        .cfi_personality 0, personality
+        .cfi_lsda 0, .Lexception0
+        nop
+        .cfi_endproc
+
+        .section ".lsda","a"
+        .p2align 2
+.Lexception0:
+lsda:
+        .byte 0
+
+        .section ".text.personality","ax"
+personality:
+        nop
diff --git a/lld/test/ELF/gc-sections-lsda.s b/lld/test/ELF/gc-sections-lsda.s
--- a/lld/test/ELF/gc-sections-lsda.s
+++ b/lld/test/ELF/gc-sections-lsda.s
@@ -12,10 +12,14 @@
 # CHECK-NEXT: removing unused section {{.*}}.o:(.gcc_except_table._Z6comdatv)
 # CHECK-NEXT: removing unused section {{.*}}.o:(.gcc_except_table._Z9linkorderv)
 
-## An unused non-group non-SHF_LINK_ORDER .gcc_except_table is not discarded.
+## An unused non-group non-SHF_LINK_ORDER .gcc_except_table is also discarded.
 
 # RUN: ld.lld --gc-sections --print-gc-sections -u _Z6comdatv -u _Z9linkorderv %t.o -o /dev/null | \
-# RUN:   FileCheck /dev/null --implicit-check-not=.gcc_except_table
+# RUN:   FileCheck %s --check-prefix=CHECK2 --implicit-check-not=.gcc_except_table
+
+# CHECK2:      removing unused section {{.*}}.o:(.text)
+# CHECK2-NEXT: removing unused section {{.*}}.o:(.text._Z3foov)
+# CHECK2-NEXT: removing unused section {{.*}}.o:(.gcc_except_table._Z3foov)
 
 ## If the text sections are live, the .gcc_except_table sections are retained as
 ## well because they are referenced by .eh_frame pieces.