[ELF] - Teach ICF to take FDEs into account when doing code folding.

[grimar]

Summary

ICF currently does not take in account data stored in FDEs.
That means if we have 2 "identical" code sections, but one
of them does not have frame data associated or both of them has
different data, code still be folded, what is not correct.

Patch does the first step to improve the situation. It teaches ICF
to compare data stored in FDEs as well, so that only sections
that have equal FDEs are eligible to be merged.

[grimar]

• Removed unrelated change.

[ruiu]

ELF/EhFrame.cpp

67

I wonder if you actually tried this.

Do you really have to care about padding?

ELF/ICF.cpp

285

Rename equalsFde

ELF/InputSection.h

330

I strongly doubt if this is correct because the relationship between input sections and fdes is 1 to many.

[grimar]

• Addressed review comments.

ELF/EhFrame.cpp

67

Yes, please see eh-frame-hdr-icf-fde1.s testcase from this patch, it shows that 2 FDEs differs because of padding only.

ELF/ICF.cpp

285

Done.

ELF/InputSection.h

330

That is sure needs to be vector, but for start I decided to support simple case and improve it in following patches.
This patch open roads for other patches teaching ICF about handling .eh_frame data and it is already large (has 3 new testcases),
so to reduce amount of changes I supposed we can start from this ?

(FWIW having it as the simple pointer now does not break anything for us because before this patch ICF merged identical code ignoring all FDEs, but it already fixes some cases at the same time)

[ruiu]

ELF/EhFrame.cpp

67

I doubt if this is correct. There may be relocations pointing to given FDEs, and I think you need to compare these relocations too.

ELF/InputSection.h

330

I think I don't feel comfortable if you are going to check in a patch even though we know a correctness issue. Doing the right thing in this patch doesn't seem that hard.

[grimar]

• Addressed review comments.

ELF/EhFrame.cpp

67

This is correct I think, it just does not covers everything yet.
That is why I marked this patch as "first step" in description.

We need to scan relocations to compare LSDAs and also want to compare personality routines,
so want to take CIEs which contains a pointer to them in account when comparing FDEs during ICF.
That is what I want to implement after this patch.

ELF/InputSection.h

330

Done. Added testcase.

[grimar]

• Rebased.

[grimar]

Ping.

[grimar]

Ping.

[ruiu]

ELF/Driver.cpp

1102–1103

This change is dubious. ICF is not a part of writing a result, so it shouldn't be moved there.

ELF/EhFrame.cpp

67

I doubt if this is correct because this function seems to compare contents only byte-by-byte. You need to handle relocations right?

[grimar]

• Addressed review comments.

ELF/Driver.cpp

1102–1103

Ok. I moved createSyntheticSections and combineEhFrameSections before doIcf.

ELF/EhFrame.cpp

67

I have already answered the same question here:
https://reviews.llvm.org/D38319#inline-335138

[ruiu]

ELF/EhFrame.cpp

67

That URL just jumps to the top of the page to me.

[grimar]

ELF/EhFrame.cpp

67

Probably becaue this comment is hidden for you in phab view ? It was Mon, Oct 2, 1:39 PM:

"This is correct I think, it just does not covers everything yet.
That is why I marked this patch as "first step" in description.

We need to scan relocations to compare LSDAs and also want to compare personality routines,
so want to take CIEs which contains a pointer to them in account when comparing FDEs during ICF.
That is what I want to implement after this patch."

[ruiu]

ELF/EhFrame.cpp

67

I'd like to know how you'd scan relocations. If you have a patch, can you upload?

[grimar]

ELF/EhFrame.cpp

67

Not yet. Can try to do it and show you.

[ruiu]

ELF/EhFrame.cpp

67

It's worth doing. When I implement a feature, I often do it several times locally to see what is the best way of doing it.

[grimar]

ELF/EhFrame.cpp

67

I would like to clarify, do you think we can go in that direction for now (and then I'll try to update this with relocations scanning) or we would like to put this on hold for a while since honestly it is not clear for me with what "[RFC] Making .eh_frame more linker-friendly" can end up ?

[ruiu]

I don't think I want to add this much complexity to the linker to solve the problem that we need to split section contents that the compiler merged for no obvious reason. We should instead make the compiler not to merge sections in the first place. Thus the proposal.

[grimar]

Abandoning for now basing on recent comments.

ELF/Driver.cpp

template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   if (Config->DefineCommon)
     createCommonSections<ELFT>();
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
   if (Config->GcSections)
     markLive<ELFT>();
   decompressAndMergeSections();
-  if (Config->ICF)
-    doIcf<ELFT>();
 
   // Write the result to the file.
   writeResult<ELFT>();
 }

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);
+bool equalsFdes(ArrayRef<EhSectionPiece *> A, ArrayRef<EhSectionPiece *> B);
+
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/EhFrame.cpp

 };
 }
 
 template <class ELFT>
 size_t elf::readEhRecordSize(InputSectionBase *S, size_t Off) {
   return EhReader<ELFT>(S, S->Data.slice(Off)).readEhRecordSize();
 }
 
+static bool equalsFde(EhSectionPiece *A, EhSectionPiece *B) {
+  // We want to compare FDEs contents, for that we want to ignore
+  // CIE pointer field which used to get offset of the start of the
+  // associated CIE and therefore is fickle. We also ignore length
+  // field which can differ because of padding.
+  ArrayRef<uint8_t> DataA = A->data().drop_front(4 + 4);
+  ArrayRef<uint8_t> DataB = B->data().drop_front(4 + 4);
+  if (DataA.size() == DataB.size())
+    return DataA == DataB;
+
+  // FDEs may contain padding at the end which should not affect comparsion.
+  size_t AlignedSizeA = alignTo(DataA.size(), Config->Wordsize);
+  size_t AlignedSizeB = alignTo(DataB.size(), Config->Wordsize);
+  if (AlignedSizeA != AlignedSizeB)
+    return false;
+
+  if (DataA.size() > DataB.size())
+    std::swap(DataA, DataB);
+
+  // Check data before possible padding bytes.
+  if (memcmp(DataA.data(), DataB.data(), DataA.size()))
+    return false;
+
+  // If tail is filled with zeroes, it is padding.
+  return llvm::all_of(DataB.drop_front(DataA.size()),
+                      [](uint8_t C) { return C == 0; });
+}
+
+bool elf::equalsFdes(ArrayRef<EhSectionPiece *> A,
+                     ArrayRef<EhSectionPiece *> B) {
+  if (A.size() != B.size())
+    return false;
+  for (size_t I = 0, E = A.size(); I != E; ++I)
+    if (!equalsFde(A[I], B[I]))
+      return false;
+  return true;
+}
+
 // .eh_frame section is a sequence of records. Each record starts with
 // a 4 byte length field. This function reads the length.
 template <class ELFT> size_t EhReader<ELFT>::readEhRecordSize() {
   const endianness E = ELFT::TargetEndianness;
   if (D.size() < 4)
     failOn(D.data(), "CIE/FDE too small");
 
   // First 4 bytes of CIE/FDE is the size of the record.

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 "SymbolTable.h"
+#include "SyntheticSections.h"
 #include "Threads.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Object/ELF.h"
 #include <algorithm>
 #include <atomic>
 
 using namespace lld;
template <class ELFT> static uint32_t getHash(InputSection *S) {
   return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
 }
 
 // Returns true if section S is subject of ICF.
 static bool isEligible(InputSection *S) {
   // .init and .fini contains instructions that must be executed to
   // initialize and finalize the process. They cannot and should not
   // be merged.
-  return S->Live && (S->Flags & SHF_ALLOC) && (S->Flags & SHF_EXECINSTR) &&
-         !(S->Flags & SHF_WRITE) && S->Name != ".init" && S->Name != ".fini";
+  return S->Live && !isa<SyntheticSection>(S) && (S->Flags & SHF_ALLOC) &&
+         (S->Flags & SHF_EXECINSTR) && !(S->Flags & SHF_WRITE) &&
+         S->Name != ".init" && S->Name != ".fini";
 }
 
 // Split an equivalence class into smaller classes.
 template <class ELFT>
 void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
   // This loop rearranges sections in [Begin, End) so that all sections
   // that are equal in terms of equals{Constant,Variable} are contiguous
   // in [Begin, End).

 // Compare "non-moving" part of two InputSections, namely everything
 // except relocation targets.
 template <class ELFT>
 bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
   if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
       A->getSize() != B->getSize() || A->Data != B->Data)
     return false;
 
+  if (!equalsFdes(A->Fdes, B->Fdes))
+    return false;
+
   if (A->AreRelocsRela)
     return constantEq(A, A->template relas<ELFT>(), B,
                       B->template relas<ELFT>());
   return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
 }
 
 // Compare two lists of relocations. Returns true if all pairs of
 // relocations point to the same section in terms of ICF.

ELF/InputSection.h

struct EhSectionPiece {
 
   ArrayRef<uint8_t> data() { return {Sec->Data.data() + this->InputOff, Size}; }
 
   size_t InputOff;
   ssize_t OutputOff = -1;
   InputSectionBase *Sec;
   uint32_t Size;
   unsigned FirstRelocation;
+
+  // Keeps section where function accociated with FDE resides.
+  InputSection* FdeTargetSec = nullptr;
 };
 
 // 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,
                  StringRef Name);
public:
   InputSectionBase *getRelocatedSection();
 
   template <class ELFT, class RelTy>
   void relocateNonAlloc(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
 
   // Used by ICF.
   uint32_t Class[2] = {0, 0};
 
+  std::vector<EhSectionPiece *> Fdes;
+
   // Called by ICF to merge two input sections.
   void replace(InputSection *Other);
 
 private:
   template <class ELFT, class RelTy>
   void copyRelocations(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
 
   template <class ELFT> void copyShtGroup(uint8_t *Buf);

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

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,
+// There is one FDE per function. Returns section where function lives.
+template <class ELFT, class RelTy>
+static InputSection *getFdeTargetSection(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];
   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;
+  if (DefinedRegular *DR = dyn_cast<DefinedRegular>(&B))
+      return cast_or_null<InputSection>(DR->Section);
+  return nullptr;
+}
+
+// There is one FDE per function. Returns true if a given FDE
+// points to a live function.
+static bool isFdeLive(EhSectionPiece &Fde) {
+  return Fde.FdeTargetSec && Fde.FdeTargetSec->Repl->Live;
 }
 
 // .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>
if (ID == 0) {
       continue;
     }
 
     uint32_t CieOffset = Offset + 4 - ID;
     CieRecord *Rec = OffsetToCie[CieOffset];
     if (!Rec)
       fatal(toString(Sec) + ": invalid CIE reference");
 
-    if (!isFdeLive(Piece, Rels))
-      continue;
+    Piece.FdeTargetSec = getFdeTargetSection<ELFT>(Piece, Rels);
+    if (Piece.FdeTargetSec)
+      Piece.FdeTargetSec->Fdes.push_back(&Piece);
+
     Rec->Fdes.push_back(&Piece);
-    NumFdes++;
   }
 }
 
 template <class ELFT>
 void EhFrameSection<ELFT>::addSection(InputSectionBase *C) {
   auto *Sec = cast<EhInputSection>(C);
   Sec->Parent = this;
   updateAlignment(Sec->Alignment);
if (this->Size)
     return; // Already finalized.
 
   size_t Off = 0;
   for (CieRecord *Rec : CieRecords) {
     Rec->Cie->OutputOff = Off;
     Off += alignTo(Rec->Cie->Size, Config->Wordsize);
 
     for (EhSectionPiece *Fde : Rec->Fdes) {
+      if (!isFdeLive(*Fde))
+        continue;
       Fde->OutputOff = Off;
       Off += alignTo(Fde->Size, Config->Wordsize);
+      ++NumFdes;
     }
   }
 
   // The LSB standard does not allow a .eh_frame section with zero
   // Call Frame Information records. Therefore add a CIE record length
   // 0 as a terminator if this .eh_frame section is empty.
   if (Off == 0)
     Off = 4;

 
 template <class ELFT> void EhFrameSection<ELFT>::writeTo(uint8_t *Buf) {
   const endianness E = ELFT::TargetEndianness;
   for (CieRecord *Rec : CieRecords) {
     size_t CieOffset = Rec->Cie->OutputOff;
     writeCieFde<ELFT>(Buf + CieOffset, Rec->Cie->data());
 
     for (EhSectionPiece *Fde : Rec->Fdes) {
+      if (!isFdeLive(*Fde))
+        continue;
+
       size_t Off = Fde->OutputOff;
       writeCieFde<ELFT>(Buf + Off, Fde->data());
 
       // FDE's second word should have the offset to an associated CIE.
       // Write it.
       write32<E>(Buf + Off + 4, Off + 4 - CieOffset);
     }
   }
 
   for (EhInputSection *S : Sections)
     S->relocateAlloc(Buf, nullptr);
 
   // Construct .eh_frame_hdr. .eh_frame_hdr is a binary search table
   // to get a FDE from an address to which FDE is applied. So here
   // we obtain two addresses and pass them to EhFrameHdr object.
   if (In<ELFT>::EhFrameHdr) {
     for (CieRecord *Rec : CieRecords) {
       uint8_t Enc = getFdeEncoding<ELFT>(Rec->Cie);
       for (EhSectionPiece *Fde : Rec->Fdes) {
+        if (!isFdeLive(*Fde))
+          continue;
         uint64_t Pc = getFdePc(Buf, Fde->OutputOff, Enc);
         uint64_t FdeVA = getParent()->Addr + Fde->OutputOff;
         In<ELFT>::EhFrameHdr->addFde(Pc, FdeVA);
       }
     }
   }
 }
 

ELF/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
 #include "Config.h"
 #include "Filesystem.h"
+#include "ICF.h"
 #include "LinkerScript.h"
 #include "MapFile.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Relocations.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"

 template <class ELFT> void Writer<ELFT>::run() {
   // Create linker-synthesized sections such as .got or .plt.
   // Such sections are of type input section.
   createSyntheticSections();
 
   if (!Config->Relocatable)
     combineEhFrameSections<ELFT>();
 
+  if (Config->ICF)
+    doIcf<ELFT>();
+
   // We need to create some reserved symbols such as _end. Create them.
   if (!Config->Relocatable)
     addReservedSymbols();
 
   // Create output sections.
   if (Script->Opt.HasSections) {
     // If linker script contains SECTIONS commands, let it create sections.
     Script->processCommands(Factory);

test/ELF/eh-frame-hdr-icf-fde1.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --eh-frame-hdr --verbose | FileCheck %s
+
+## Check we have 2 equal FDEs with different size
+## because of padding in input object.
+# RUN: llvm-objdump %t --dwarf=frames | FileCheck %s --check-prefix=OBJ
+# OBJ: .debug_frame contents:
+# OBJ:    {{.*}} 00000010 {{.*}} FDE
+# OBJ:    {{.*}} 00000014 {{.*}} FDE
+
+## Check ICF merges sections with the same FDE data even when
+## size is different because of padding bytes.
+# CHECK:      selected .text.f1
+# CHECK-NEXT:  removed .text.f2
+
+.global personality
+.hidden personality
+personality:
+ nop
+
+.section .text.f1, "ax"
+.cfi_startproc
+.cfi_personality 0x1b, personality
+nop
+.cfi_endproc
+
+.section .text.f2, "ax"
+.cfi_startproc
+.cfi_personality 0x1b, personality
+nop
+.cfi_endproc
+

test/ELF/eh-frame-hdr-icf-fde2.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --eh-frame-hdr --verbose | FileCheck %s
+
+## Check ICF does not merge sections with different FDE data.
+# CHECK-NOT: selected
+
+## Check we have 2 different FDEs in output.
+# RUN: llvm-objdump %t2 --dwarf=frames | FileCheck %s --check-prefix=FRAMES
+# FRAMES: .eh_frame contents:
+# FRAMES:   00000018 00000014 0000001c FDE cie=0000001c pc=00000e68...00000e69
+# FRAMES:   00000030 00000014 00000034 FDE cie=00000034 pc=00000e51...00000e52
+
+.section .text.f1, "ax"
+.cfi_startproc
+nop
+.cfi_endproc
+
+.section .text.f2, "ax"
+.cfi_startproc
+.cfi_adjust_cfa_offset 8
+nop
+.cfi_endproc

test/ELF/eh-frame-hdr-icf-fde3.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --verbose | FileCheck %s
+
+## Check we do not apply ICF for synthetic sections. (empty .plt and .text in this case)
+# CHECK-NOT: selected

test/ELF/eh-frame-hdr-icf-fde4.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --verbose | FileCheck %s
+
+## In this test each section has 2 FDEs attached.
+## .text.f1 and .text.f3 has equal FDEs and second FDE of.text.f2 section
+## is different. Check we merge .text.f1 and .text.f3 together.
+
+# CHECK-NOT:  .text.f2
+# CHECK:      selected .text.f1
+# CHECK-NEXT:  removed .text.f3
+# CHECK-NOT:  .text.f2
+
+.section .text.f1, "ax"
+.cfi_startproc
+nop
+.cfi_endproc
+nop
+nop
+.cfi_startproc
+nop
+nop
+nop
+.cfi_endproc
+
+.section .text.f2, "ax"
+.cfi_startproc
+nop
+.cfi_endproc
+nop
+nop
+.cfi_startproc
+.cfi_adjust_cfa_offset 8
+nop
+nop
+nop
+.cfi_endproc
+
+.section .text.f3, "ax"
+.cfi_startproc
+nop
+.cfi_endproc
+nop
+nop
+.cfi_startproc
+nop
+nop
+nop
+.cfi_endproc

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

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: ld.lld %t -o %t2 --icf=all --eh-frame-hdr
 # RUN: llvm-objdump -s %t2 | FileCheck %s
 
 # CHECK: Contents of section .eh_frame_hdr:
-# CHECK-NEXT: 200158 011b033b 1c000000 01000000 a80e0000
+# CHECK-NEXT: 200158 011b033b 1c000000 01000000 a90e0000
 #                                      ^ FDE count
 # CHECK-NEXT: 200168 38000000 00000000 00000000
 #                    ^ FDE for f2
 
 .globl _start, f1, f2
 _start:
   ret