[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

211–212 ↗

(On Diff #114363)

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

105 ↗

(On Diff #114363)

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.

120 ↗

(On Diff #114363)

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

301–302 ↗

(On Diff #114363)

EhInputSections are scanned multiple times?

[ikudrin]

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

[ikudrin]

ELF/EhFrame.cpp

211–212 ↗

(On Diff #114363)

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

ELF/MarkLive.cpp

105 ↗

(On Diff #114363)

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

301–302 ↗

(On Diff #114363)

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

118–121 ↗

(On Diff #115406)

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

[ikudrin]

Refactored scanEhFrameSection.

[ikudrin]

Formatted.

[ruiu]

ELF/MarkLive.cpp

152–154 ↗

(On Diff #115663)

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

180–182 ↗

(On Diff #115663)

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.

220–221 ↗

(On Diff #115663)

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

228 ↗

(On Diff #115663)

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

349 ↗

(On Diff #115663)

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

447–462 ↗

(On Diff #115663)

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 ↗

(On Diff #115663)

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.

349 ↗

(On Diff #115663)

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

447–462 ↗

(On Diff #115663)

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 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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

131 ↗

(On Diff #116180)

We usually call this It.

145 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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

165–166 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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 ↗

(On Diff #120207)

We usually write public members first.

115 ↗

(On Diff #120207)

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 ↗

(On Diff #116180)

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 ↗

(On Diff #116180)

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?

lld/ELF/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "lld/Common/Memory.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Object/ELF.h"

 private:
   void splitStrings(StringRef s, size_t size);
   void splitNonStrings(ArrayRef<uint8_t> a, size_t size);
 };
 
 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};
   }
 
   size_t inputOff;
   ssize_t outputOff = -1;
   InputSectionBase *sec;
-  uint32_t size;
+  uint32_t size : 31;
+  uint32_t 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,

lld/ELF/MarkLive.cpp

 
 namespace {
 template <class ELFT> class MarkLive {
 public:
   MarkLive(unsigned partition) : partition(partition) {}
 
   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);
   void markSymbol(Symbol *sym);
   void mark();
 
   template <class RelTy>
   void resolveReloc(InputSectionBase &sec, RelTy &rel, bool fromFDE);
 
   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;
 
   // A list of sections to visit.
   SmallVector<InputSection *, 0> queue;
 
   // There are normally few input sections whose names are valid C
   // identifiers, so we just store a SmallVector instead of a multimap.
   DenseMap<StringRef, SmallVector<InputSectionBase *, 0>> cNamedSections;
 };
 } // 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) {
   return target->getImplicitAddend(sec.content().begin() + rel.r_offset,
                                    rel.getType(config->isMips64EL));
 }
 
 template <class ELFT>
for (InputSectionBase *sec : cNamedSections.lookup(sym.getName()))
     enqueue(sec, 0);
 }
 
 // The .eh_frame section is an unfortunate special case.
 // The section is divided in CIEs and FDEs and the relocations it 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.
+// 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;
-    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);
-  }
+    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;
+    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.
 static bool isReserved(InputSectionBase *sec) {
   switch (sec->type) {
   case SHT_FINI_ARRAY:
template <class ELFT> void MarkLive<ELFT>::run() {
   markSymbol(symtab.find(config->entry));
   markSymbol(symtab.find(config->init));
   markSymbol(symtab.find(config->fini));
   for (StringRef s : config->undefined)
     markSymbol(symtab.find(s));
   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);
       continue;
     }
     if (sec->flags & SHF_LINK_ORDER)
       continue;
 
if (isReserved(sec) || script->shouldKeep(sec)) {
       cNamedSections[saver().save("__start_" + sec->name)].push_back(sec);
       cNamedSections[saver().save("__stop_" + sec->name)].push_back(sec);
     }
   }
 
   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()) {
     InputSectionBase &sec = *queue.pop_back_val();
 
     const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
     for (const typename ELFT::Rel &rel : rels.rels)
       resolveReloc(sec, rel, false);
for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart)
     MarkLive<ELFT>(curPart).run();
 
   // If we have multiple partitions, some sections need to live in the main
   // partition even if they were allocated to a loadable partition. Move them
   // there now.
   if (partitions.size() != 1)
     MarkLive<ELFT>(1).moveToMain();
 
+  MarkLive<ELFT>(1).processEhFrameSections();
+
   // Report garbage-collected sections.
   if (config->printGcSections)
     for (InputSectionBase *sec : ctx.inputSections)
       if (!sec->isLive())
         message("removing unused section " + toString(sec));
 }
 
 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

lld/ELF/SyntheticSections.h

 template <typename ELFT> void writeEhdr(uint8_t *buf, Partition &part);
 template <typename ELFT> void writePhdrs(uint8_t *buf, Partition &part);
 
 Defined *addSyntheticLocal(StringRef name, uint8_t type, uint64_t value,
                            uint64_t size, InputSectionBase &section);
 
 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;
   uint64_t nameStrTab;
 
   std::unique_ptr<SyntheticSection> elfHeader;
   std::unique_ptr<SyntheticSection> programHeaders;
   SmallVector<PhdrEntry *, 0> phdrs;

lld/ELF/SyntheticSections.cpp

CieRecord *EhFrameSection::addCie(EhSectionPiece &cie, ArrayRef<RelTy> rels) {
   if (!rec) {
     rec = make<CieRecord>();
     rec->cie = &cie;
     cieRecords.push_back(rec);
   }
   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;
 
   // 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 nullptr;
 
   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;
 }
 
 // .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, 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)
       fatal(toString(sec) + ": invalid CIE reference");
 
     if (!isFdeLive<ELFT>(fde, rels))
       continue;
     rec->fdes.push_back(&fde);

 template class elf::PartitionElfHeaderSection<ELF32BE>;
 template class elf::PartitionElfHeaderSection<ELF64LE>;
 template class elf::PartitionElfHeaderSection<ELF64BE>;
 
 template class elf::PartitionProgramHeadersSection<ELF32LE>;
 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);

lld/test/ELF/eh-frame-gc3.s

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

lld/test/ELF/gc-sections-lsda.s

 # REQUIRES: x86
 # RUN: llvm-mc %s -o %t.o -filetype=obj -triple=x86_64-pc-linux
 
 ## Discard an unused .gcc_except_table in a COMDAT group or having SHF_LINK_ORDER
 ## if the associated text section is discarded.
 
 # RUN: ld.lld --gc-sections --print-gc-sections -u _Z3foov %t.o -o /dev/null | \
 # RUN:   FileCheck %s --implicit-check-not=.gcc_except_table
 
 # CHECK:      removing unused section {{.*}}.o:(.text._Z6comdatv)
 # CHECK-NEXT: removing unused section {{.*}}.o:(.text._Z9linkorderv)
 # 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.
 
 # RUN: ld.lld --gc-sections --print-gc-sections -u _Z3foov -u _Z6comdatv -u _Z9linkorderv %t.o -o /dev/null | \
 # RUN:   FileCheck %s --check-prefix=KEEP
 
 # KEEP-NOT: .gcc_except_table