[ELF] Scan .eh_frame sections precisely in order to eliminate unused LSDAs and personality routines.

[krisb]

Summary

This patch marks CIEs, LSDAs and personality routines with all their dependent sections
only if they are used in the main part of a program.

[ruiu]

ELF/EhFrame.cpp

210–211

This is not new code, but does an FDE without any relocation make sense? If not, maybe we should report an error instead of marking them to be ignored by -1?

ELF/MarkLive.cpp

173

I do not fully understand this function probably because I do not fully understand the relationship between CIE, FDE, LSDA, personality functions, etc. Can you rewrite this comment so that this function is understandable for those who don't know the structure of .eh_frame? I don't think we need a lengthy comment here, but the current comment seems to require too much prior knowledge.

192

I'm worried if the hash table is too slow. Can you avoid using it?

351–352

EhInputSections are scanned multiple times?

[ikudrin]

• Substituted a sorted vector for a DenseMap.
• Improved (hopefully) comments.

[ikudrin]

ELF/EhFrame.cpp

210–211

The polite behavior was introduced by @rafael to handle gold's '-r' output, see https://reviews.llvm.org/rL295141.

ELF/MarkLive.cpp

173

I've tried to extend the comment. How do you find it now?

351–352

A personality routine, which might be added in this scanning, depends on other functions which might not be added yet. These functions might also have EH information and so on. However, I suppose that it should converge quickly.

[ikudrin]

Update the patch to incorporate the latest changes in the master branch.

[ruiu]

ELF/MarkLive.cpp

186–189

This function seems to get too long. Can you refactor?

[ikudrin]

Refactored scanEhFrameSection.

[ikudrin]

Formatted.

[ruiu]

ELF/MarkLive.cpp

152–154

Do you really need to care about that? It doesn't seem at least harmful to call Fn on the described function.

180–182

Is this code reachable? The GC traverses a graph consists of nodes (sections, fdes, cies, etc.) and edges (relocations). I wonder who can point to this dangling cie.

204–205

It is probably better to check if Piece->Live outside processFde and rename processFde scanFde.

212

Likewise, I'd check Cie->Live before calling the function and rename the function scanCie.

348–364

How many times does this loop usually repeat? Since this loop scans all EhInputSections on every iteration, I'm a bit worried about its performance.

ELF/SyntheticSections.cpp

448–463

It is odd that you had to check use Live and isFdeLive. If GC works correctly, all live sections are marked as such, so you don't need to use isFdeLive, no? I believe how this should work.

[ikudrin]

• Update to the current tip.
• Address review comments.

[grimar]

Added llvm-commits. to subscribers because otherwise notifications about this patch were never shown in mailing lists..

[ikudrin]

ELF/MarkLive.cpp

180–182

It's not a dangling CIE. It just doesn't refer to a personality function, which is not prohibited.
And the edge from an FDE to a CIE is not a relocation, but an indirect link through ID field in the FDE.

348–364

In case of programs which do not use EH, like clang or lld, there will be only one iteration.
A typical executable with EH on Linux, where a personal routine is located in a DSO, will require two iterations. And a new flag ExecInQueue helps to avoid scanning EH frames for the second time.
If a personality routine is added from a library, it'll require two full iterations, but hardly more, because all references should be satisfied at that point.

ELF/SyntheticSections.cpp

448–463

When --gc-sections is not specified, we mark all pieces alive by default. In that case markLive() is not called and we have to check the state here to discard FDEs for merged COMDAT sections, for example.

[ikudrin]

Ping. Is there anything I can do to proceed the patch?

[ruiu]

Sorry for the belated response. This patch seemed a bit too complicated to me, and I was thinking if there's a better way of doing it.

So, there are two tricky things in garbage-collecting .eh_frame section contents:

1. .eh_frame sections consists of multiple section pieces, and each piece can be alive or dead. This is different from a regular section because a regular section is alive or dead as a whole.
2. .eh_frame sections have reverse dependency to .text sections. Usually, if a section A has a relocation pointing to B, then B is alive if A is alive. However, for .eh_frame section pieces, this liveness propagates backwards.

To deal with the above problems, you scan all .eh_frame section pieces in this patch. So, our algorithm with this patch is no longer a simple graph traversal algorithm. I think that's the reason why it feels a bit too complicated to me. But I think if you add data members to InputSection for reverse dependencies, you can keep it as a simple graph traversal.

How about this?

1. Add a new member, EhSectionPieces vector, to InputSection. It holds the input section's FDEs and CIEs if exists. At the beginning of markLive, scan all .eh_frame sections to initialize the vectors.
2. To represent edges between InputSections through .eh_frame section pieces, explicitly add these dependencies to InputSection::DependentSections. For example, if a function has .eh_frame pieces, its personality function is added to its DependentSection. You can initialize it at the beginning of markLive.

After doing the above two things, all dependencies are explicitly represented, and all you have to do is to traverse the graph, make .eh_frame pieces alive, and visit DependentSections as usual. I think this is a cleaner way of doing garbage-collecting.

ELF/InputSection.h

276

If unsigned is not uint32_t, a padding would be created between Size and Live, so you should make Live uint32_t.

Also, sizeof(uint32_t) is 32, so 8 * sizeof(uint32_t) - 1 is always just 31.

uint32_t Size : 31;
uint32_t Live : 1;

ELF/MarkLive.cpp

125

We do not sprinkle const that much in lld if a local variable is obviously not mutated.

131

We usually call this It.

145

const typename ELFT::uint -> uint64_t

You can always use uint64_t to represent a value that can be either 32 or 64 bit.

148–150

This loop can be written as

for (unsigned I = Fde.FirstRelocation + 1, N = Rels.size(); I < N && Rels[I].r_offset < FdeEnd; ++I)
    resolveReloc<ELFT>(EH, Rels[I], Fn);

164

I wouldn't assign it to a temporary local variable.

165–166

I still doubt if this check makes sense. If we visit an invalid CIE that doesn't point to anything and mark it alive, then that means we are going to emit an invalid CIE to the output file, no? It seems it is an error condition.

269–271

Isn't this a premature optimization? I wouldn't add this unless it is proved to be actually effective.

[ikudrin]

Addressed review comments.

[ikudrin]

In D37626#882892, @ruiu wrote:

How about this?

1. Add a new member, EhSectionPieces vector, to InputSection. It holds the input section's FDEs and CIEs if exists. At the beginning of markLive, scan all .eh_frame sections to initialize the vectors.
2. To represent edges between InputSections through .eh_frame section pieces, explicitly add these dependencies to InputSection::DependentSections. For example, if a function has .eh_frame pieces, its personality function is added to its DependentSection. You can initialize it at the beginning of markLive.

After doing the above two things, all dependencies are explicitly represented, and all you have to do is to traverse the graph, make .eh_frame pieces alive, and visit DependentSections as usual. I think this is a cleaner way of doing garbage-collecting.

I tried to implement this approach, see D38391. I hope I understood your suggestion right.

According to my tests, it is slower than the current version, approximately, by 10-20%. I checked it both with samples which use (like omnetpp) and do not use EH (like clang). I compared the execution time of markLive() alone, not the whole linker.

ELF/MarkLive.cpp

165–166

It's not a dangling or invalid CIE. It just doesn't refer to a personality function, which is not prohibited. For example, you can find such CIEs in any LLVM project on Linux, because they do not use exception handling.

269–271

I don't think so. It really helps to avoid the second scan of EH frames in most cases.

[ruiu]

Yes, https://reviews.llvm.org/D38391 is what I was thinking about. Thank you for creating that patch. Do you know why that is slower than this patch? My wild guess is that it is because D38391 needs to add a lot of pointers to EhSectionPieces vectors, but I wonder if that's actually the case.

[ikudrin]

I guess the same. Moreover:

• This patch process any CIE once while D38391 has to store a pointer to it for each corresponding input section.
• D38391 also stores pointers to personality function sections and LSDA sections for each input section which use them.

This variant might be slower than D38391 only if it has to scan EH frames several times, which is quite a rare case.

[ikudrin]

Ping. Is there anything I can do to improve this patch? I suppose I am hardly able to make D38391 quicker than this one.

• Rebase on the current tip.

[ruiu]

I still want to explore the idea of https://reviews.llvm.org/D38391 instead of this because that approach seems more "correct" to me, and this patch seems fairly complex. We may end up with this patch insetad of D38391, but it should be worth a try to reduce complexity.

ELF/MarkLive.cpp

50–52

We usually write public members first.

120

This needs a function comment. If I understand it correctly, this function takes an FDE and returns an CIE that the given FDE belongs to. Is this correct?

269–271

But how much time you can save? I feel like we shouldn't optimize it at the moment.

[ikudrin]

• Address review comments;
• Rebase on the tip.

[ikudrin]

I believe that the complexity in both cases is similar. Here we have two kinds of edges with distinct traversal functions. There we have to convert these edges in advance so that we can use only one traversal function. And distinct traversal function is not that different from the conversion function. But conversion always requires additional space and time to store edges, while the traversal function might be called several times. But my opinion might be biased.

ELF/MarkLive.cpp

269–271

According to my tests, with this optimization the execution time of doGcSections() becomes about 1% longer if the linked program does not use EH (like clang) and about 2.5% shorter in the other case (like omnetpp). The effect is not significant, so I've removed it.

[ruiu]

I started a discussion in the llvm-dev mailing list to eliminate the need to scan .eh_frame sections in a special way. Please send a comment there if you have one.

[ikudrin]

Hello @ruiu,

In D37626#908500, @ruiu wrote:

I started a discussion in the llvm-dev mailing list to eliminate the need to scan .eh_frame sections in a special way. Please send a comment there if you have one.

Could you summarise the discussion here, please?

[krisb]

Let's give this another chance.

[krisb]

Rebase on ToT

[krisb]

Ping

[MaskRay]

I am still on a trip and will take a few days more.

[MaskRay]

Can you describe the motivation of this change? It has two parts:

• Personality routine GC
• LSDA GC

Personality routine GC is typically not useful at all. (Moreover, in many configurations (without -static-libstdc++) personality routines are in shared objects.)

If you specify -fbinutils-version=2.36 (or latest), .gcc_except_table.* sections can be GCed.
I currently lean toward the opinion that this patch is probably not useful.
There is some GC complexity which does not pay off.

About the implementation, I think there are two issues:

• for (EhInputSection *eh : ctx.ehInputSections) { loop can just be executed once, not nested in a for (;;) loop.
• Calling isFdeLive twice, once in MarkLive, once in EhFrameSection::addRecords is not great.

[krisb]

Hello @MaskRay, thanks for the review! And sorry for the delay with response.
The patch is useful in a probably rare case, indeed. It reproduces with a statically linked application that does not use exceptions itself, but hooks the personality routine because of some indirect dependencies that are removed by GC. Unfortunately, we cannot share our sample, but we will try to find something meaningful in the public domain.
Note that GNU ld produces smaller binaries because it analyzes the liveness of sections/pieces more thoroughly.

[MaskRay]

In D37626#4170599, @krisb wrote:

Hello @MaskRay, thanks for the review! And sorry for the delay with response.
The patch is useful in a probably rare case, indeed. It reproduces with a statically linked application that does not use exceptions itself, but hooks the personality routine because of some indirect dependencies that are removed by GC. Unfortunately, we cannot share our sample, but we will try to find something meaningful in the public domain.
Note that GNU ld produces smaller binaries because it analyzes the liveness of sections/pieces more thoroughly.

Can you try -fbinutils-version=2.36 or latest?

ELF/EhFrame.h

 
 namespace lld {
 namespace elf {
 class InputSectionBase;
 struct EhSectionPiece;
 
 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
 
 #endif

ELF/EhFrame.cpp

 // That means the linker has to understand the format of the section.
 //
 // This file contains a few utility functions to read .eh_frame contents.
 //
 //===----------------------------------------------------------------------===//
 
 #include "EhFrame.h"
 #include "Error.h"
+#include "InputFiles.h"
 #include "InputSection.h"
 #include "Relocations.h"
 #include "Strings.h"
 
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/Endian.h"
 
if (C == 'L') {
       readByte();
       continue;
     }
     failOn(Aug.data(), "unknown .eh_frame augmentation string: " + Aug);
   }
   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);
 template size_t elf::readEhRecordSize<ELF64BE>(InputSectionBase *S, size_t Off);
 
 template uint8_t elf::getFdeEncoding<ELF32LE>(EhSectionPiece *P);
 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);

ELF/InputSection.h

private:
   mutable llvm::once_flag InitOffsetMap;
 
   llvm::DenseSet<uint64_t> LiveOffsets;
 };
 
 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;
 };
 
 // This corresponds to a .eh_frame section of an input file.
 class EhInputSection : public InputSectionBase {
 public:
   template <class ELFT>
   EhInputSection(ObjFile<ELFT> *F, const typename ELFT::Shdr *Header,

ELF/MarkLive.cpp

 // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
 // by default. Starting with GC-root symbols or sections, markLive function
 // defined in this file visits all reachable sections to set their Live
 // bits. Writer will then ignore sections whose Live bits are off, so that
 // such sections are not included into output.
 //
 //===----------------------------------------------------------------------===//
 
+#include "EhFrame.h"
 #include "InputSection.h"
 #include "LinkerScript.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/ELF.h"
 #include <functional>
 #include <vector>
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 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) {
   return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset,
                                    Rel.getType(Config->IsMips64EL));
 }
 
 template <class ELFT>
if (Sec.AreRelocsRela) {
     for (const typename ELFT::Rel &Rel : Sec.template rels<ELFT>())
       resolveReloc<ELFT>(Sec, Rel, Fn);
   }
 
   for (InputSectionBase *IS : Sec.DependentSections)
     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);
   }
 }
 
 template <class ELFT>
 static void
 scanEhFrameSection(EhInputSection &EH,
                    std::function<void(InputSectionBase *, uint64_t)> Fn) {
   if (!EH.NumRelocations)

 }
 
 // This is the main function of the garbage collector.
 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 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
     // the ELF spec doesn't allow a relocation to point to a deduplicated
     // COMDAT section directly. Unfortunately this happens in practice (e.g.
     // .eh_frame) so we need to add a check.
     if (Sec == &InputSection::Discarded)
       return;
 
     // We don't gc non alloc sections.
     if (!(Sec->Flags & SHF_ALLOC))
       return;
 
     // Usually, a whole section is marked as live or dead, but in mergeable
     // (splittable) sections, each piece of data has independent liveness bit.
     // So we explicitly tell it which offset is in use.
     if (auto *MS = dyn_cast<MergeInputSection>(Sec))
       MS->markLiveAt(Offset);
 
     if (Sec->Live)
       return;
     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) {
     if (auto *D = dyn_cast_or_null<DefinedRegular>(Sym)) {
       if (auto *IS = cast_or_null<InputSectionBase>(D->Section))
         Enqueue(IS, D->Value);
       return;
     }
for (StringRef S : Script->Opt.ReferencedSymbols)
     MarkSymbol(Symtab->find(S));
 
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
   for (Symbol *S : Symtab->getSymbols())
     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))
       Enqueue(Sec, 0);
     else if (isValidCIdentifier(Sec->Name)) {
       CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
       CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec);
     }
   }
 
   // Mark all reachable sections.
+  // 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>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

ELF/SyntheticSections.h

 private:
   uint64_t Size = 0;
   template <class RelTy>
   void addSectionAux(EhInputSection *S, llvm::ArrayRef<RelTy> Rels);
 
   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;
 
   // CIE records are uniquified by their contents and personality functions.
   llvm::DenseMap<std::pair<ArrayRef<uint8_t>, SymbolBody *>, CieRecord *>
       CieMap;
 };

ELF/SyntheticSections.cpp

 // synthetic sections are created either output sections or input sections,
 // but we are rewriting code so that all synthetic sections are created as
 // input sections.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SyntheticSections.h"
 #include "Config.h"
+#include "EhFrame.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "LinkerScript.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "Target.h"
CieRecord *EhFrameSection<ELFT>::addCie(EhSectionPiece &Cie,
   if (!Rec) {
     Rec = make<CieRecord>();
     Rec->Cie = &Cie;
     CieRecords.push_back(Rec);
   }
   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
 // one and associates FDEs to the CIE.
 template <class ELFT>
 template <class RelTy>
 void EhFrameSection<ELFT>::addSectionAux(EhInputSection *Sec,
                                          ArrayRef<RelTy> Rels) {
   const endianness E = ELFT::TargetEndianness;
 
   DenseMap<size_t, CieRecord *> OffsetToCie;
   for (EhSectionPiece &Piece : Sec->Pieces) {
     // The empty record is the end marker.
     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) {
       OffsetToCie[Offset] = addCie(Piece, Rels);
       continue;
     }
 
     uint32_t CieOffset = Offset + 4 - ID;
     CieRecord *Rec = OffsetToCie[CieOffset];
     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++;
   }
 }
 
 template <class ELFT>
 void EhFrameSection<ELFT>::addSection(InputSectionBase *C) {

test/ELF/eh-frame-gc3.s

+// 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

test/ELF/gc-sections-lsda.s

 // REQUIRES: x86
 
 // RUN: llvm-mc %s -o %t.o -filetype=obj -triple=x86_64-pc-linux
 // RUN: ld.lld -shared --gc-sections %t.o -o %t
 
 // Test that we handle .eh_frame keeping sections alive. We could be more
 // precise and gc the entire contents of this file, but test that at least
 // 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
         .section        .abc,"a"
 zed:
         .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: