[ELF] --icf: don't fold text sections with LSDA

[MaskRay]

Summary

Fix PR36272 and PR46835

A .eh_frame FDE references a text section and (optionally) a LSDA (in
.gcc_except_table). Even if two text sections have identical content and
relocations (e.g. a() and b()), we cannot fold them if their LSDA are different.

void foo();
void a() {
  try { foo(); } catch (int) { }
}
void b() {
  try { foo(); } catch (float) { }
}

Scan .eh_frame pieces with LSDA and disallow referenced text sections to be
folded. If two .gcc_except_table have identical semantics (usually identical
content with PC-relative encoding), we will lose folding opportunity.
For ClickHouse (an exception-heavy application), this can reduce --icf=all efficiency
from 9% to 5%. There may be some percentage we can reclaim without affecting
correctness, if we analyze .eh_frame and .gcc_except_table sections.

gold 2.24 implemented a more complex fix (resolution to
https://sourceware.org/bugzilla/show_bug.cgi?id=21066) which combines the
checksum of .eh_frame CIE/FDE pieces.

[MaskRay]

Simplify

[grimar]

lld/ELF/EhFrame.cpp

215

I'd put this first as it is what you are looking for:

for (char c : aug) {
  if (c == 'L')
    return true;
...
}

lld/ELF/ICF.cpp

466

Did you perform a test of a some project that uses exceptions? I wonder if it is really that rare.

473

It is probably more natural for this to be llvm::DenseSet<size_t>?

E.g:

llvm::DenseSet<size_t> ciesWithLDSA;
...
    if (id == 0 && hasLSDA(piece)) {
      ciesWithLDSA.insert(offset);
      continue;
    }
    uint32_t cieOffset = offset + 4 - id;
    if (!ciesWithLDSA.contains(cieOffset))
      continue;
...

481

The Length can take either 4 or 12 bytes (extended length). Should this be handled?

496

It's a bit strange to see that eqClass[0] is set to xxHash64(s->data() right above,
but handleLSDA might override the value to 1,2...N?

Should the hash be combined into, e.g. like combineRelocHashes does?

lld/ELF/SyntheticSections.cpp

373–374

I think the comment should describe the Defined symbol returned.
A non-null pointer sounds like it can be any !nullptr.

[MaskRay]

Address comments

lld/ELF/EhFrame.cpp

215

Emm. I tend to prefer the order where compilers usually generate the augmentation string.

lld/ELF/ICF.cpp

481

The extended length format .eh_frame is not supported by MC (lib/MC/MCDwarf.cpp:EmitFDE).

The previous function does not handle the extended length as well.

Personally I think it is rarer than DWARF64

"A 8 byte unsigned value indicating the length in bytes of the CIE structure, not
including the Length and Extended Length fields themselves" It is hard to get a single CIE structure larger than 4GiB. This is different from DWARF64 where the FDE field is an absolute offset instead of a PC-relative offset (so the total size of .debug_frame matters)

496

Not necessary. By assigning 1,2,...,N, we don't actually want such sections to be folded into others. The combine operation is redundant.

[MaskRay]

Move iterateFDEWithLSDA to SyntheticSections.cpp

[MaskRay]

Small adjustment

[amosbird]

I've compared three version of lld by linking clickhouse with -fexceptions and --icf=all. Here are the stripped binary size of the related outputs:

bytes	binary
259837744	clickhouse	<---- clang12 (patch)
249643904	clickhouse	<---- clang12 (no-patch)
249643824	clickhouse	<---- clang10
275773152	clickhouse	<---- clang12 ( --icf=none)
260764432	clickhouse	<---- gold 1.16
276295792	clickhouse	<---- gold 1.16 ( --icf=none)

[grimar]

In D84610#2177862, @amosbird wrote:

I've compared three version of lld by linking clickhouse with -fexceptions and --icf=all. Here are the stripped binary size of the related outputs:

bytes	binary
259837744	clickhouse	<---- clang12 (patch)
249643904	clickhouse	<---- clang12 (no-patch)

259837744 / 249643904 = 1,04x, i.e +4%

[MaskRay]

Remove the sentence "they are rare"

Note that clang uses a monolithic .gcc_except_table (this actually has a problem with RISC-V -mrelax), two functions with LSDA will likely reference different offsets of .gcc_except_table . We can't ICF them unless we parse .gcc_except_table (which is not great).

ClickHouse is an exception-heavy project. As you can see, the ICF efficiency dropped from 9% to 5%. However, this cost is probably something we have to take. Currently we can't guarantee safety. Many projects don't use much exception. They would not be affected much.

[MaskRay]

😳

[grimar]

lld/ELF/ICF.cpp

496

It is just strange to see that we drop the xxHash64 work that was done, it looks excessive.

Right above we have the following code:

auto *s = cast<InputSection>(sec);
if (isEligible(s))
  sections.push_back(s);`

I've not checked, but have you considered something like not putting those sections into sections list at all?
I.e. make them non-eligible for ICF from the begining?

[MaskRay]

Simplify

[MaskRay]

lld/ELF/ICF.cpp

496

Good idea. Simplified.

[grimar]

LGTM I think. Would be very nice to see another opinion though.

[psmith]

I agree I think it is best to err on the side of correctness. As I understand it we could do better (merge more sections) but this would involve pulling apart .eh_frame sections to show equivalence. I think that could come later.

[thakis]

This probably breaks the build on systems where uint64_t and size_t are different types, such as apparently on macOS:

http://45.33.8.238/mac/18492/step_4.txt

I'm only seeing this on some of my Macs though, so maybe it's dependent on sdk or host clang version. If the error makes sense to you, do something about it, else I'll try installing a newer host clang on that bot later.

[MaskRay]

In D84610#2198191, @thakis wrote:

This probably breaks the build on systems where uint64_t and size_t are different types, such as apparently on macOS:

http://45.33.8.238/mac/18492/step_4.txt

I'm only seeing this on some of my Macs though, so maybe it's dependent on sdk or host clang version. If the error makes sense to you, do something about it, else I'll try installing a newer host clang on that bot later.

Already fixed by 279e4cf78262dfef560631d643b85aa2032ac566

[MaskRay]

In D84610#2198195, @MaskRay wrote:

In D84610#2198191, @thakis wrote:

This probably breaks the build on systems where uint64_t and size_t are different types, such as apparently on macOS:

http://45.33.8.238/mac/18492/step_4.txt

I'm only seeing this on some of my Macs though, so maybe it's dependent on sdk or host clang version. If the error makes sense to you, do something about it, else I'll try installing a newer host clang on that bot later.

Already fixed by 279e4cf78262dfef560631d643b85aa2032ac566

I will make a follow-up patch changing these size_t to uint64_t. They are so error-prone.

lld/ELF/EhFrame.h

 
 namespace lld {
 namespace elf {
 class InputSectionBase;
 struct EhSectionPiece;
 
 size_t readEhRecordSize(InputSectionBase *s, size_t off);
 uint8_t getFdeEncoding(EhSectionPiece *p);
+bool hasLSDA(const EhSectionPiece &p);
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/EhFrame.cpp

 using namespace lld::elf;
 
 namespace {
 class EhReader {
 public:
   EhReader(InputSectionBase *s, ArrayRef<uint8_t> d) : isec(s), d(d) {}
   size_t readEhRecordSize();
   uint8_t getFdeEncoding();
+  bool hasLSDA();
 
 private:
   template <class P> void failOn(const P *loc, const Twine &msg) {
     fatal("corrupted .eh_frame: " + msg + "\n>>> defined in " +
           isec->getObjMsg((const uint8_t *)loc - isec->data().data()));
   }
 
   uint8_t readByte();
   void skipBytes(size_t count);
   StringRef readString();
   void skipLeb128();
   void skipAugP();
+  StringRef getAugmentation();
 
   InputSectionBase *isec;
   ArrayRef<uint8_t> d;
 };
 }
 
 size_t elf::readEhRecordSize(InputSectionBase *s, size_t off) {
   return EhReader(s, s->data().slice(off)).readEhRecordSize();
if (size >= d.size())
     failOn(d.data() - 1, "corrupted CIE");
   d = d.slice(size);
 }
 
 uint8_t elf::getFdeEncoding(EhSectionPiece *p) {
   return EhReader(p->sec, p->data()).getFdeEncoding();
 }
 
-uint8_t EhReader::getFdeEncoding() {
+bool elf::hasLSDA(const EhSectionPiece &p) {
+  return EhReader(p.sec, p.data()).hasLSDA();
+}
+
+StringRef EhReader::getAugmentation() {
   skipBytes(8);
   int version = readByte();
   if (version != 1 && version != 3)
     failOn(d.data() - 1,
            "FDE version 1 or 3 expected, but got " + Twine(version));
 
   StringRef aug = readString();
 
   // Skip code and data alignment factors.
   skipLeb128();
   skipLeb128();
 
   // Skip the return address register. In CIE version 1 this is a single
   // byte. In CIE version 3 this is an unsigned LEB128.
   if (version == 1)
     readByte();
   else
     skipLeb128();
+  return aug;
+}
 
+uint8_t EhReader::getFdeEncoding() {
   // We only care about an 'R' value, but other records may precede an 'R'
   // record. Unfortunately records are not in TLV (type-length-value) format,
   // so we need to teach the linker how to skip records for each type.
+  StringRef aug = getAugmentation();
   for (char c : aug) {
     if (c == 'R')
       return readByte();
     if (c == 'z') {
       skipLeb128();
       continue;
     }
     if (c == 'P') {
       skipAugP();
       continue;
     }
     if (c == 'L') {
       readByte();
       continue;
     }
     failOn(aug.data(), "unknown .eh_frame augmentation string: " + aug);
   }
   return DW_EH_PE_absptr;
 }
+
+bool EhReader::hasLSDA() {
+  StringRef aug = getAugmentation();
+  for (char c : aug) {
+    if (c == 'L')
+      return true;
+    if (c == 'z')
+      skipLeb128();
+    else if (c == 'P')
+      skipAugP();
+    else if (c == 'R')
+      readByte();
+    else
+      failOn(aug.data(), "unknown .eh_frame augmentation string: " + aug);
+  }
+  return false;
+}

lld/ELF/ICF.cpp

 // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
 // in the Gold Linker
 // http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
 //
 //===----------------------------------------------------------------------===//
 
 #include "ICF.h"
 #include "Config.h"
+#include "EhFrame.h"
 #include "LinkerScript.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Writer.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/BinaryFormat/ELF.h"
private:
 
   size_t findBoundary(size_t begin, size_t end);
 
   void forEachClassRange(size_t begin, size_t end,
                          llvm::function_ref<void(size_t, size_t)> fn);
 
   void forEachClass(llvm::function_ref<void(size_t, size_t)> fn);
 
+  void handleLSDA(EhFrameSection &eh);
+
   std::vector<InputSection *> sections;
 
   // We repeat the main loop while `Repeat` is true.
   std::atomic<bool> repeat;
 
   // The main loop counter.
   int cnt = 0;
 
static void combineRelocHashes(unsigned cnt, InputSection *isec,
   isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
 }
 
 static void print(const Twine &s) {
   if (config->printIcfSections)
     message(s);
 }
 
+// Two text sections may have identical content and relocations but different
+// LSDA, e.g. the two functions may have catch blocks of different types. If a
+// text section is referenced by a .eh_frame FDE with LSDA, we assign a unique
+// hash to it so that it will not be folded into another section. This is
+// implemented by iterating over CIE/FDE and assigning a unique ID to the
+// referenced text section from a live FDE.
+//
+// If two .gcc_except_table have identical semantics (usually identical content
+// with PC-relative encoding), we will lose folding opportunity but such cases
+// are rare.
+template <class ELFT> void ICF<ELFT>::handleLSDA(EhFrameSection &eh) {
+  uint32_t uniqueId = 0;
+  eh.iterateFDEWithLSDA<ELFT>(
+      [&](InputSection &s) { s.eqClass[0] = ++uniqueId; });
+}
+
 // The main function of ICF.
 template <class ELFT> void ICF<ELFT>::run() {
   // Compute isPreemptible early. We may add more symbols later, so this loop
   // cannot be merged with the later computeIsPreemptible() pass which is used
   // by scanRelocations().
   for (Symbol *sym : symtab->symbols())
     sym->isPreemptible = computeIsPreemptible(*sym);
 
   // Collect sections to merge.
   for (InputSectionBase *sec : inputSections) {
     auto *s = cast<InputSection>(sec);
     if (isEligible(s))
       sections.push_back(s);
   }
 
   // Initially, we use hash values to partition sections.
   parallelForEach(
       sections, [&](InputSection *s) { s->eqClass[0] = xxHash64(s->data()); });
 
+  // Assign unique hash values to text sections with LSDA.
+  for (Partition &part : partitions)
+    handleLSDA(*part.ehFrame);
+
+  // Perform 2 rounds of relocation hash propagation. 2 is an empirical value to
+  // reduce the average sizes of equivalence classes, i.e. segregate() which has
+  // a large time complexity will have less work to do.
   for (unsigned cnt = 0; cnt != 2; ++cnt) {
     parallelForEach(sections, [&](InputSection *s) {
       if (s->areRelocsRela)
         combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
       else
         combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
     });
   }

lld/ELF/InputSection.h

private:
   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) {}
 
-  ArrayRef<uint8_t> data() {
+  ArrayRef<uint8_t> data() const {
     return {sec->data().data() + this->inputOff, size};
   }
 
   size_t inputOff;
   ssize_t outputOff = -1;
   InputSectionBase *sec;
   uint32_t size;
   unsigned firstRelocation;

lld/ELF/SyntheticSections.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_SYNTHETIC_SECTIONS_H
 #define LLD_ELF_SYNTHETIC_SECTIONS_H
 
 #include "DWARF.h"
 #include "EhFrame.h"
 #include "InputSection.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/Endian.h"
 #include <functional>
 
 namespace lld {
 namespace elf {
 class Defined;
public:
   struct FdeData {
     uint32_t pcRel;
     uint32_t fdeVARel;
   };
 
   std::vector<FdeData> getFdeData() const;
   ArrayRef<CieRecord *> getCieRecords() const { return cieRecords; }
 
+  template <class ELFT, class RelTy>
+  Defined *isFdeLive(EhSectionPiece &piece, ArrayRef<RelTy> rels);
+  template <class ELFT>
+  void iterateFDEWithLSDA(llvm::function_ref<void(InputSection &)> fn);
+
 private:
   // This is used only when parsing EhInputSection. We keep it here to avoid
   // allocating one for each EhInputSection.
   llvm::DenseMap<size_t, CieRecord *> offsetToCie;
 
   uint64_t size = 0;
 
   template <class ELFT, class RelTy>
   void addRecords(EhInputSection *s, llvm::ArrayRef<RelTy> rels);
-  template <class ELFT>
-  void addSectionAux(EhInputSection *s);
-
+  template <class ELFT> void addSectionAux(EhInputSection *s);
   template <class ELFT, class RelTy>
-  CieRecord *addCie(EhSectionPiece &piece, ArrayRef<RelTy> rels);
+  void iterateFDEWithLSDAAux(EhInputSection &sec, ArrayRef<RelTy> rels,
+                             llvm::DenseSet<size_t> &ciesWithLSDA,
+                             llvm::function_ref<void(InputSection &)> fn);
 
   template <class ELFT, class RelTy>
-  bool isFdeLive(EhSectionPiece &piece, ArrayRef<RelTy> rels);
+  CieRecord *addCie(EhSectionPiece &piece, ArrayRef<RelTy> rels);
 
   uint64_t getFdePc(uint8_t *buf, size_t off, uint8_t enc) const;
 
   std::vector<CieRecord *> cieRecords;
 
   // CIE records are uniquified by their contents and personality functions.
   llvm::DenseMap<std::pair<ArrayRef<uint8_t>, Symbol *>, CieRecord *> cieMap;
 };

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 true if a given FDE
-// points to a live function.
+// There is one FDE per function. Returns a non-null pointer to the function
+// symbol if a given FDE points to a live function.
 template <class ELFT, class RelTy>
-bool EhFrameSection::isFdeLive(EhSectionPiece &fde, ArrayRef<RelTy> rels) {
+Defined *EhFrameSection::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;
+    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 (SectionBase *sec = d->section)
-      return sec->partition == partition;
-  return false;
+    if (d->section && 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) {
void EhFrameSection::addSection(EhInputSection *sec) {
 
   alignment = std::max(alignment, sec->alignment);
   sections.push_back(sec);
 
   for (auto *ds : sec->dependentSections)
     dependentSections.push_back(ds);
 }
 
+// Used by ICF<ELFT>::handleLSDA(). This function is very similar to
+// EhFrameSection::addRecords().
+template <class ELFT, class RelTy>
+void EhFrameSection::iterateFDEWithLSDAAux(
+    EhInputSection &sec, ArrayRef<RelTy> rels, DenseSet<size_t> &ciesWithLSDA,
+    llvm::function_ref<void(InputSection &)> fn) {
+  for (EhSectionPiece &piece : sec.pieces) {
+    // Skip ZERO terminator.
+    if (piece.size == 4)
+      continue;
+
+    size_t offset = piece.inputOff;
+    uint32_t id =
+        endian::read32<ELFT::TargetEndianness>(piece.data().data() + 4);
+    if (id == 0) {
+      if (hasLSDA(piece))
+        ciesWithLSDA.insert(offset);
+      continue;
+    }
+    uint32_t cieOffset = offset + 4 - id;
+    if (ciesWithLSDA.count(cieOffset) == 0)
+      continue;
+
+    // The CIE has a LSDA argument. Assign a unique ID to eqClass[0] of the
+    // defining section.
+    if (Defined *d = isFdeLive<ELFT>(piece, rels))
+      if (auto *s = dyn_cast_or_null<InputSection>(d->section))
+        fn(*s);
+  }
+}
+
+template <class ELFT>
+void EhFrameSection::iterateFDEWithLSDA(
+    llvm::function_ref<void(InputSection &)> fn) {
+  DenseSet<uint64_t> ciesWithLSDA;
+  for (EhInputSection *sec : sections) {
+    ciesWithLSDA.clear();
+    if (sec->areRelocsRela)
+      iterateFDEWithLSDAAux<ELFT>(*sec, sec->template relas<ELFT>(),
+                                  ciesWithLSDA, fn);
+    else
+      iterateFDEWithLSDAAux<ELFT>(*sec, sec->template rels<ELFT>(),
+                                  ciesWithLSDA, fn);
+  }
+}
+
 static void writeCieFde(uint8_t *buf, ArrayRef<uint8_t> d) {
   memcpy(buf, d.data(), d.size());
 
   size_t aligned = alignTo(d.size(), config->wordsize);
 
   // Zero-clear trailing padding if it exists.
   memset(buf + d.size(), 0, aligned - d.size());
 

 template class elf::MipsAbiFlagsSection<ELF64LE>;
 template class elf::MipsAbiFlagsSection<ELF64BE>;
 
 template class elf::MipsOptionsSection<ELF32LE>;
 template class elf::MipsOptionsSection<ELF32BE>;
 template class elf::MipsOptionsSection<ELF64LE>;
 template class elf::MipsOptionsSection<ELF64BE>;
 
+template void EhFrameSection::iterateFDEWithLSDA<ELF32LE>(
+    function_ref<void(InputSection &)>);
+template void EhFrameSection::iterateFDEWithLSDA<ELF32BE>(
+    function_ref<void(InputSection &)>);
+template void EhFrameSection::iterateFDEWithLSDA<ELF64LE>(
+    function_ref<void(InputSection &)>);
+template void EhFrameSection::iterateFDEWithLSDA<ELF64BE>(
+    function_ref<void(InputSection &)>);
+
 template class elf::MipsReginfoSection<ELF32LE>;
 template class elf::MipsReginfoSection<ELF32BE>;
 template class elf::MipsReginfoSection<ELF64LE>;
 template class elf::MipsReginfoSection<ELF64BE>;
 
 template class elf::DynamicSection<ELF32LE>;
 template class elf::DynamicSection<ELF32BE>;
 template class elf::DynamicSection<ELF64LE>;

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

+# REQUIRES: x86
+## Test that text sections with LSDA are not folded.
+
+## Test REL.
+# RUN: llvm-mc -filetype=obj -triple=i386 %s -o %t1.o
+# RUN: ld.lld --icf=all %t1.o -o /dev/null --print-icf-sections | FileCheck %s --implicit-check-not=removing
+## Test RELA.
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t2.o
+# RUN: ld.lld --icf=all %t2.o -o /dev/null --print-icf-sections | FileCheck %s --implicit-check-not=removing
+
+# CHECK:      selected section {{.*}}.o:(.text.Z1cv)
+# CHECK-NEXT:   removing identical section {{.*}}.o:(.text.Z1dv)
+
+.globl _Z1av, _Z1bv, _Z1cv, _Z1dv
+.section .text.Z1av,"ax",@progbits
+_Z1av:
+  .cfi_startproc
+  .cfi_lsda 27, .Lexception0
+  ret
+  .cfi_endproc
+
+.section .text.Z1bv,"ax",@progbits
+_Z1bv:
+  .cfi_startproc
+  .cfi_lsda 27, .Lexception0
+  ret
+  .cfi_endproc
+
+.section .text.Z1cv,"ax",@progbits
+_Z1cv:
+  .cfi_startproc
+  ret
+  .cfi_endproc
+
+.section .text.Z1dv,"ax",@progbits
+_Z1dv:
+  .cfi_startproc
+  ret
+  .cfi_endproc
+
+.section .gcc_except_table,"a",@progbits
+## The actual content does not matter.
+.Lexception0: