ELF: Teach ICF about relocations referring to merge input sections.

[pcc]

Summary

Relocations referring to merge sections are considered equal if they
resolve to the same offset in the same output section.

Depends on D34093

[ruiu]

lld/ELF/ICF.cpp

216 ↗

(On Diff #102142)

write it in two lines.

[pcc]

• Address review comment

[ruiu]

LGTM

lld/trunk/ELF/ICF.cpp

 template <class ELFT> class ICF {
 public:
   void run();
 
 private:
   void segregate(size_t Begin, size_t End, bool Constant);
 
   template <class RelTy>
-  bool constantEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB);
+  bool constantEq(const InputSection *A, ArrayRef<RelTy> RelsA,
+                  const InputSection *B, ArrayRef<RelTy> RelsB);
 
   template <class RelTy>
   bool variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
                   const InputSection *B, ArrayRef<RelTy> RelsB);
 
   bool equalsConstant(const InputSection *A, const InputSection *B);
   bool equalsVariable(const InputSection *A, const InputSection *B);
 
while (Begin < End) {
 
     Begin = Mid;
   }
 }
 
 // Compare two lists of relocations.
 template <class ELFT>
 template <class RelTy>
-bool ICF<ELFT>::constantEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB) {
-  auto Eq = [](const RelTy &A, const RelTy &B) {
-    return A.r_offset == B.r_offset &&
-           A.getType(Config->IsMips64EL) == B.getType(Config->IsMips64EL) &&
-           getAddend<ELFT>(A) == getAddend<ELFT>(B);
+bool ICF<ELFT>::constantEq(const InputSection *A, ArrayRef<RelTy> RelsA,
+                           const InputSection *B, ArrayRef<RelTy> RelsB) {
+  auto Eq = [&](const RelTy &RA, const RelTy &RB) {
+    if (RA.r_offset != RB.r_offset ||
+        RA.getType(Config->IsMips64EL) != RB.getType(Config->IsMips64EL))
+      return false;
+    uint64_t AddA = getAddend<ELFT>(RA);
+    uint64_t AddB = getAddend<ELFT>(RB);
+
+    SymbolBody &SA = A->template getFile<ELFT>()->getRelocTargetSym(RA);
+    SymbolBody &SB = B->template getFile<ELFT>()->getRelocTargetSym(RB);
+    if (&SA == &SB)
+      return AddA == AddB;
+
+    auto *DA = dyn_cast<DefinedRegular>(&SA);
+    auto *DB = dyn_cast<DefinedRegular>(&SB);
+    if (!DA || !DB)
+      return false;
+
+    // Relocations referring to absolute symbols are constant-equal if their
+    // values are equal.
+    if (!DA->Section || !DB->Section)
+      return !DA->Section && !DB->Section &&
+             DA->Value + AddA == DB->Value + AddB;
+
+    if (DA->Section->kind() != DB->Section->kind())
+      return false;
+
+    // Relocations referring to InputSections are constant-equal if their
+    // section offsets are equal.
+    if (isa<InputSection>(DA->Section))
+      return DA->Value + AddA == DB->Value + AddB;
+
+    // Relocations referring to MergeInputSections are constant-equal if their
+    // offsets in the output section are equal.
+    auto *X = dyn_cast<MergeInputSection>(DA->Section);
+    if (!X)
+      return false;
+    auto *Y = cast<MergeInputSection>(DB->Section);
+    if (X->getParent() != Y->getParent())
+      return false;
+
+    uint64_t OffsetA =
+        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
+    uint64_t OffsetB =
+        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
+    return OffsetA == OffsetB;
   };
 
   return RelsA.size() == RelsB.size() &&
          std::equal(RelsA.begin(), RelsA.end(), RelsB.begin(), Eq);
 }
 
 // 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 (A->AreRelocsRela)
-    return constantEq(A->template relas<ELFT>(), B->template relas<ELFT>());
-  return constantEq(A->template rels<ELFT>(), B->template rels<ELFT>());
+    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.
 template <class ELFT>
 template <class RelTy>
 bool ICF<ELFT>::variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
                            const InputSection *B, ArrayRef<RelTy> RelsB) {
   auto Eq = [&](const RelTy &RA, const RelTy &RB) {
     // The two sections must be identical.
     SymbolBody &SA = A->template getFile<ELFT>()->getRelocTargetSym(RA);
     SymbolBody &SB = B->template getFile<ELFT>()->getRelocTargetSym(RB);
     if (&SA == &SB)
       return true;
 
-    auto *DA = dyn_cast<DefinedRegular>(&SA);
-    auto *DB = dyn_cast<DefinedRegular>(&SB);
-    if (!DA || !DB)
-      return false;
-    if (DA->Value != DB->Value)
-      return false;
-
-    // Either both symbols must be absolute...
-    if (!DA->Section || !DB->Section)
-      return !DA->Section && !DB->Section;
+    auto *DA = cast<DefinedRegular>(&SA);
+    auto *DB = cast<DefinedRegular>(&SB);
 
-    // Or the two sections must be in the same equivalence class.
+    // We already dealt with absolute and non-InputSection symbols in
+    // constantEq, and for InputSections we have already checked everything
+    // except the equivalence class.
+    if (!DA->Section)
+      return true;
     auto *X = dyn_cast<InputSection>(DA->Section);
-    auto *Y = dyn_cast<InputSection>(DB->Section);
-    if (!X || !Y)
-      return false;
+    if (!X)
+      return true;
+    auto *Y = cast<InputSection>(DB->Section);
 
     // Ineligible sections are in the special equivalence class 0.
     // They can never be the same in terms of the equivalence class.
     if (X->Class[Current] == 0)
       return false;
 
     return X->Class[Current] == Y->Class[Current];
   };

lld/trunk/test/ELF/Inputs/icf-merge-sec.s

+.section .rodata.str,"aMS",@progbits,1
+.asciz "bar"
+.asciz "baz"
+.asciz "foo"
+
+.section .text.f2,"ax"
+.globl f2
+f2:
+.quad .rodata.str+8

lld/trunk/test/ELF/Inputs/icf-merge.s

+.section .rodata.str,"aMS",@progbits,1
+.asciz "bar"
+.asciz "baz"
+foo:
+.asciz "foo"
+
+.section .text.f2,"ax"
+.globl f2
+f2:
+lea foo+42(%rip), %rax

lld/trunk/test/ELF/Inputs/icf-merge2.s

+.section .rodata.str,"aMS",@progbits,1
+.asciz "bar"
+.asciz "baz"
+boo:
+.asciz "boo"
+
+.section .text.f2,"ax"
+.globl f2
+f2:
+lea boo+42(%rip), %rax

lld/trunk/test/ELF/Inputs/icf-merge3.s

+.section .rodata.str,"aMS",@progbits,1
+.asciz "bar"
+.asciz "baz"
+foo:
+.asciz "foo"
+
+.section .text.f2,"ax"
+.globl f2
+f2:
+lea foo+43(%rip), %rax

lld/trunk/test/ELF/icf-merge-sec.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-merge-sec.s -o %t2
+# RUN: ld.lld %t %t2 -o %t3 --icf=all --verbose | FileCheck %s
+
+# CHECK: selected .text.f1
+# CHECK:   removed .text.f2
+
+.section .rodata.str,"aMS",@progbits,1
+.asciz "foo"
+.asciz "string 1"
+.asciz "string 2"
+
+.section .text.f1,"ax"
+.globl f1
+f1:
+.quad .rodata.str

lld/trunk/test/ELF/icf-merge.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-merge.s -o %t1
+# RUN: ld.lld %t %t1 -o %t1.out --icf=all --verbose | FileCheck %s
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-merge2.s -o %t2
+# RUN: ld.lld %t %t2 -o %t3.out --icf=all --verbose | FileCheck --check-prefix=NOMERGE %s
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-merge3.s -o %t3
+# RUN: ld.lld %t %t3 -o %t3.out --icf=all --verbose | FileCheck --check-prefix=NOMERGE %s
+
+# CHECK: selected .text.f1
+# CHECK:   removed .text.f2
+
+# NOMERGE-NOT: selected .text.f
+
+.section .rodata.str,"aMS",@progbits,1
+foo:
+.asciz "foo"
+.asciz "string 1"
+.asciz "string 2"
+
+.section .text.f1,"ax"
+.globl f1
+f1:
+lea foo+42(%rip), %rax