Index: ELF/EhFrame.h
===================================================================
--- ELF/EhFrame.h
+++ ELF/EhFrame.h
@@ -19,6 +19,8 @@
 
 template <class ELFT> size_t readEhRecordSize(InputSectionBase *S, size_t Off);
 template <class ELFT> uint8_t getFdeEncoding(EhSectionPiece *P);
+template <class ELFT, class RelTy>
+bool isFdeLive(EhSectionPiece &Fde, ArrayRef<RelTy> Rels);
 } // namespace elf
 } // namespace lld
 
Index: ELF/EhFrame.cpp
===================================================================
--- ELF/EhFrame.cpp
+++ ELF/EhFrame.cpp
@@ -18,6 +18,7 @@
 
 #include "EhFrame.h"
 #include "Error.h"
+#include "InputFiles.h"
 #include "InputSection.h"
 #include "Relocations.h"
 #include "Strings.h"
@@ -200,6 +201,29 @@
   return DW_EH_PE_absptr;
 }
 
+// There is one FDE per function. Returns true if a given FDE
+// points to a live function.
+template <class ELFT, class RelTy>
+bool elf::isFdeLive(EhSectionPiece &Fde, ArrayRef<RelTy> Rels) {
+  auto *Sec = cast<EhInputSection>(Fde.Sec);
+  unsigned FirstRelI = Fde.FirstRelocation;
+
+  // An FDE should point to some function because FDEs are to describe
+  // functions. That's however not always the case due to an issue of
+  // ld.gold with -r. ld.gold may discard only functions and leave their
+  // corresponding FDEs, which results in creating bad .eh_frame sections.
+  // To deal with that, we ignore such FDEs.
+  if (FirstRelI == (unsigned)-1)
+    return false;
+
+  const RelTy &Rel = Rels[FirstRelI];
+  SymbolBody &B = Sec->template getFile<ELFT>()->getRelocTargetSym(Rel);
+  if (auto *D = dyn_cast<DefinedRegular>(&B))
+    if (D->Section)
+      return cast<InputSectionBase>(D->Section)->Repl->Live;
+  return false;
+}
+
 template size_t elf::readEhRecordSize<ELF32LE>(InputSectionBase *S, size_t Off);
 template size_t elf::readEhRecordSize<ELF32BE>(InputSectionBase *S, size_t Off);
 template size_t elf::readEhRecordSize<ELF64LE>(InputSectionBase *S, size_t Off);
@@ -209,3 +233,20 @@
 template uint8_t elf::getFdeEncoding<ELF32BE>(EhSectionPiece *P);
 template uint8_t elf::getFdeEncoding<ELF64LE>(EhSectionPiece *P);
 template uint8_t elf::getFdeEncoding<ELF64BE>(EhSectionPiece *P);
+
+template bool elf::isFdeLive<ELF32LE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF32LE::Rel> Rels);
+template bool elf::isFdeLive<ELF32LE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF32LE::Rela> Rels);
+template bool elf::isFdeLive<ELF32BE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF32BE::Rel> Rels);
+template bool elf::isFdeLive<ELF32BE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF32BE::Rela> Rels);
+template bool elf::isFdeLive<ELF64LE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF64LE::Rel> Rels);
+template bool elf::isFdeLive<ELF64LE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF64LE::Rela> Rels);
+template bool elf::isFdeLive<ELF64BE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF64BE::Rel> Rels);
+template bool elf::isFdeLive<ELF64BE>(EhSectionPiece &Fde,
+                                      ArrayRef<ELF64BE::Rela> Rels);
Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -264,14 +264,16 @@
 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() { return {Sec->Data.data() + this->InputOff, Size}; }
 
   size_t InputOff;
   ssize_t OutputOff = -1;
   InputSectionBase *Sec;
-  uint32_t Size;
+  uint32_t Size : 8 * sizeof(uint32_t) - 1;
+  unsigned Live : 1;
   unsigned FirstRelocation;
 };
 
Index: ELF/MarkLive.cpp
===================================================================
--- ELF/MarkLive.cpp
+++ ELF/MarkLive.cpp
@@ -20,6 +20,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "EhFrame.h"
 #include "InputSection.h"
 #include "LinkerScript.h"
 #include "Memory.h"
@@ -42,6 +43,16 @@
 using namespace lld;
 using namespace lld::elf;
 
+namespace {
+class EhFrameSectionCies {
+  std::vector<EhSectionPiece *> Cies;
+
+public:
+  void add(EhSectionPiece *Cie);
+  EhSectionPiece *get(const EhSectionPiece &Fde, uint32_t ID) const;
+};
+}
+
 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase &Sec,
                                      const typename ELFT::Rel &Rel) {
@@ -101,52 +112,113 @@
     Fn(IS, 0);
 }
 
+void EhFrameSectionCies::add(EhSectionPiece *Cie) {
+  assert(Cies.empty() || Cies.back()->InputOff < Cie->InputOff);
+  Cies.push_back(Cie);
+}
+
+EhSectionPiece *EhFrameSectionCies::get(const EhSectionPiece &Fde,
+                                        uint32_t ID) const {
+  if (Cies.empty())
+    return nullptr;
+
+  const uint32_t CieOffset = Fde.InputOff + 4 - ID;
+
+  // In most cases, a FDE refers to the most recent CIE.
+  if (Cies.back()->InputOff == CieOffset)
+    return Cies.back();
+
+  auto Found = std::lower_bound(Cies.begin(), Cies.end(), CieOffset,
+                                [](EhSectionPiece *Cie, uint32_t Offset) {
+                                  return Cie->InputOff < Offset;
+                                });
+  if (Found != Cies.end() && (*Found)->InputOff == CieOffset)
+    return *Found;
+
+  return nullptr;
+}
+
+template <class ELFT, class RelTy>
+static void scanFde(EhInputSection &EH, ArrayRef<RelTy> Rels,
+                    std::function<void(InputSectionBase *, uint64_t)> Fn,
+                    const EhSectionPiece &Fde) {
+  const typename ELFT::uint 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, N = Rels.size(); I < N; ++I) {
+    const RelTy &Rel = Rels[I];
+    if (Rel.r_offset >= FdeEnd)
+      break;
+    // In a 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<ELFT>(EH, Rel, Fn);
+  }
+}
+
+template <class ELFT, class RelTy>
+static void scanCie(EhInputSection &EH, ArrayRef<RelTy> Rels,
+                    std::function<void(InputSectionBase *, uint64_t)> Fn,
+                    const EhSectionPiece &Cie) {
+  const unsigned CieFirstRelI = Cie.FirstRelocation;
+  if (CieFirstRelI == (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<ELFT>(EH, Rels[CieFirstRelI], Fn);
+}
+
 // The .eh_frame section is an unfortunate special case.
-// The section is divided in CIEs and FDEs and the relocations it can have are
+// The section is divided in CIEs (Common Information Entries) and FDEs
+// (Frame Description Entries). Each FDE references to a corresponding
+// CIE via ID field, where a relative offset is stored.
+// The relocations the section can have are:
 // * 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.
+// * FDEs can refer to a LSDA.
+// * FDEs refer to the function they contain information about.
+// 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, class RelTy>
 static void
 scanEhFrameSection(EhInputSection &EH, ArrayRef<RelTy> Rels,
                    std::function<void(InputSectionBase *, uint64_t)> Fn) {
   const endianness E = ELFT::TargetEndianness;
 
-  for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
-    EhSectionPiece &Piece = EH.Pieces[I];
-    unsigned FirstRelI = Piece.FirstRelocation;
-    if (FirstRelI == (unsigned)-1)
-      continue;
-    if (read32<E>(Piece.data().data() + 4) == 0) {
-      // This is a CIE, we only need to worry about the first relocation. It is
-      // known to point to the personality function.
-      resolveReloc<ELFT>(EH, Rels[FirstRelI], Fn);
+  EhFrameSectionCies Cies;
+  for (EhSectionPiece &Piece : EH.Pieces) {
+    // The empty record is the end marker.
+    if (Piece.Size == 4)
+      return;
+
+    const uint32_t ID = read32<E>(Piece.data().data() + 4);
+    if (ID == 0) {
+      Cies.add(&Piece);
       continue;
     }
-    // This is a FDE. The relocations point to the described function or to
-    // a LSDA. We only need to keep the LSDA alive, so ignore anything that
-    // points to executable sections.
-    typename ELFT::uint PieceEnd = Piece.InputOff + Piece.Size;
-    for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
-      const RelTy &Rel = Rels[I2];
-      if (Rel.r_offset >= PieceEnd)
-        break;
-      resolveReloc<ELFT>(EH, Rels[I2],
-                         [&](InputSectionBase *Sec, uint64_t Offset) {
-                           if (Sec && Sec != &InputSection::Discarded &&
-                               !(Sec->Flags & SHF_EXECINSTR))
-                             Fn(Sec, 0);
-                         });
-    }
+
+    if (Piece.Live // This FDE is already fully processed.
+        || !elf::isFdeLive<ELFT>(Piece, Rels))
+      continue;
+    // This FDE should be kept.
+    Piece.Live = true;
+
+    scanFde<ELFT>(EH, Rels, Fn, Piece);
+
+    // Find the corresponding CIE
+    EhSectionPiece *Cie = Cies.get(Piece, ID);
+    if (!Cie)
+      fatal(toString(&EH) + ": invalid CIE reference");
+
+    if (Cie->Live) // Already processed.
+      continue;
+    Cie->Live = true;
+
+    scanCie<ELFT>(EH, Rels, Fn, *Cie);
   }
 }
 
@@ -194,6 +266,9 @@
 template <class ELFT> void elf::markLive() {
   SmallVector<InputSection *, 256> Q;
   CNamedSections.clear();
+  // The flag is set if an executable section is added to the queue.
+  // We scan .eh_frame sections only if the flag is set.
+  bool ExecInQueue = false;
 
   auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) {
     // Skip over discarded sections. This in theory shouldn't happen, because
@@ -218,8 +293,11 @@
     Sec->Live = true;
 
     // Add input section to the queue.
-    if (InputSection *S = dyn_cast<InputSection>(Sec))
+    if (InputSection *S = dyn_cast<InputSection>(Sec)) {
       Q.push_back(S);
+      if (S->Flags & SHF_EXECINSTR)
+        ExecInQueue = true;
+    }
   };
 
   auto MarkSymbol = [&](SymbolBody *Sym) {
@@ -247,14 +325,15 @@
     if (S->includeInDynsym())
       MarkSymbol(S->body());
 
+  std::vector<EhInputSection *> EhInputSections;
+
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (InputSectionBase *Sec : InputSections) {
-    // .eh_frame is always marked as live now, but also it can reference to
-    // sections that contain personality. We preserve all non-text sections
-    // referred by .eh_frame here.
+    // Postpone scanning .eh_frame until we find all the secions reachable
+    // from the roots.
     if (auto *EH = dyn_cast_or_null<EhInputSection>(Sec))
-      scanEhFrameSection<ELFT>(*EH, Enqueue);
+      EhInputSections.push_back(EH);
     if (Sec->Flags & SHF_LINK_ORDER)
       continue;
     if (isReserved<ELFT>(Sec) || Script->shouldKeep(Sec))
@@ -266,8 +345,23 @@
   }
 
   // Mark all reachable sections.
-  while (!Q.empty())
-    forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
+  // It should take only one or two iterations to converge.
+  // If the output does not use exception handling, scanning .eh_frame sections
+  // will not add new sections to the queue and the loop will stop.
+  // Otherwise, sections for LSDAs and a personality function will be added.
+  // The personality function might be located in a DSO or in a library.
+  // In the latter case, it might require an additional iteration because
+  // it may introduce new dependencies, which, in turn, will require
+  // an additional scan of .eh_frame sections.
+  while (true) {
+    while (!Q.empty())
+      forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
+    if (!ExecInQueue)
+      break;
+    ExecInQueue = false;
+    for (EhInputSection *EH : EhInputSections)
+      scanEhFrameSection<ELFT>(*EH, Enqueue);
+  }
 }
 
 template void elf::markLive<ELF32LE>();
Index: ELF/SyntheticSections.h
===================================================================
--- ELF/SyntheticSections.h
+++ ELF/SyntheticSections.h
@@ -95,9 +95,6 @@
   template <class RelTy>
   CieRecord *addCie(EhSectionPiece &Piece, ArrayRef<RelTy> Rels);
 
-  template <class RelTy>
-  bool isFdeLive(EhSectionPiece &Piece, ArrayRef<RelTy> Rels);
-
   uint64_t getFdePc(uint8_t *Buf, size_t Off, uint8_t Enc);
 
   std::vector<CieRecord *> CieRecords;
Index: ELF/SyntheticSections.cpp
===================================================================
--- ELF/SyntheticSections.cpp
+++ ELF/SyntheticSections.cpp
@@ -16,6 +16,7 @@
 
 #include "SyntheticSections.h"
 #include "Config.h"
+#include "EhFrame.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "LinkerScript.h"
@@ -428,31 +429,6 @@
   return Rec;
 }
 
-// There is one FDE per function. Returns true if a given FDE
-// points to a live function.
-template <class ELFT>
-template <class RelTy>
-bool EhFrameSection<ELFT>::isFdeLive(EhSectionPiece &Fde,
-                                     ArrayRef<RelTy> Rels) {
-  auto *Sec = cast<EhInputSection>(Fde.Sec);
-  unsigned FirstRelI = Fde.FirstRelocation;
-
-  // An FDE should point to some function because FDEs are to describe
-  // functions. That's however not always the case due to an issue of
-  // ld.gold with -r. ld.gold may discard only functions and leave their
-  // corresponding FDEs, which results in creating bad .eh_frame sections.
-  // To deal with that, we ignore such FDEs.
-  if (FirstRelI == (unsigned)-1)
-    return false;
-
-  const RelTy &Rel = Rels[FirstRelI];
-  SymbolBody &B = Sec->template getFile<ELFT>()->getRelocTargetSym(Rel);
-  if (auto *D = dyn_cast<DefinedRegular>(&B))
-    if (D->Section)
-      return cast<InputSectionBase>(D->Section)->Repl->Live;
-  return false;
-}
-
 // .eh_frame is a sequence of CIE or FDE records. In general, there
 // is one CIE record per input object file which is followed by
 // a list of FDEs. This function searches an existing CIE or create a new
@@ -469,6 +445,9 @@
     if (Piece.Size == 4)
       return;
 
+    if (!Piece.Live)
+      continue;
+
     size_t Offset = Piece.InputOff;
     uint32_t ID = read32<E>(Piece.data().data() + 4);
     if (ID == 0) {
@@ -481,7 +460,7 @@
     if (!Rec)
       fatal(toString(Sec) + ": invalid CIE reference");
 
-    if (!isFdeLive(Piece, Rels))
+    if (!Config->GcSections && !elf::isFdeLive<ELFT>(Piece, Rels))
       continue;
     Rec->Fdes.push_back(&Piece);
     NumFdes++;
Index: test/ELF/eh-frame-gc3.s
===================================================================
--- /dev/null
+++ test/ELF/eh-frame-gc3.s
@@ -0,0 +1,34 @@
+// 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
Index: test/ELF/gc-sections-lsda.s
===================================================================
--- test/ELF/gc-sections-lsda.s
+++ test/ELF/gc-sections-lsda.s
@@ -8,9 +8,14 @@
 // we are consistent: if we keep .abc, we have to keep .foo
 
 // RUN: llvm-readobj -s %t | FileCheck %s
-// CHECK:  Name: .abc
-// CHECK: Name: .foo
+// CHECK:     Name: .abc
+// CHECK-NOT: Name: .abc2
+// CHECK:     Name: .foo
+// CHECK-NOT: Name: .foo2
 
+        .section        .text.func,"ax"
+        .global func
+func:
         .cfi_startproc
         .cfi_lsda 0x1b,zed
         .cfi_endproc
@@ -19,3 +24,16 @@
         .long   bar-.
         .section        .foo,"ax"
 bar:
+
+// This section is similar to .text.func except that the symbol is local
+// and should be eliminated as such with all dependent sections.
+        .section        .text.func2,"ax"
+func2:
+        .cfi_startproc
+        .cfi_lsda 0x1b,zed2
+        .cfi_endproc
+        .section        .abc2,"a"
+zed2:
+        .long   bar2-.
+        .section        .foo2,"ax"
+bar2: