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

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

Differential Revision: https://reviews.llvm.org/D34094

llvm-svn: 305177

7 files changed, 146 insertions, 22 deletions

diff --git a/lld/ELF/ICF.cpp b/lld/ELF/ICF.cpp
index 536032bdc3a..09512a8b09d 100644
--- a/lld/ELF/ICF.cpp
+++ b/lld/ELF/ICF.cpp
@@ -98,7 +98,8 @@ 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,
@@ -206,11 +207,53 @@ void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
 // 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() &&
@@ -226,8 +269,9 @@ bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
     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
@@ -243,22 +287,18 @@ bool ICF<ELFT>::variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
     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.
diff --git a/lld/test/ELF/Inputs/icf-merge-sec.s b/lld/test/ELF/Inputs/icf-merge-sec.s
new file mode 100644
index 00000000000..7454e952e38
--- /dev/null
+++ b/lld/test/ELF/Inputs/icf-merge-sec.s
@@ -0,0 +1,9 @@
+.section .rodata.str,"aMS",@progbits,1
+.asciz "bar"
+.asciz "baz"
+.asciz "foo"
+
+.section .text.f2,"ax"
+.globl f2
+f2:
+.quad .rodata.str+8
diff --git a/lld/test/ELF/Inputs/icf-merge.s b/lld/test/ELF/Inputs/icf-merge.s
new file mode 100644
index 00000000000..8a099298f5c
--- /dev/null
+++ b/lld/test/ELF/Inputs/icf-merge.s
@@ -0,0 +1,10 @@
+.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
diff --git a/lld/test/ELF/Inputs/icf-merge2.s b/lld/test/ELF/Inputs/icf-merge2.s
new file mode 100644
index 00000000000..e845a6177e2
--- /dev/null
+++ b/lld/test/ELF/Inputs/icf-merge2.s
@@ -0,0 +1,10 @@
+.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
diff --git a/lld/test/ELF/Inputs/icf-merge3.s b/lld/test/ELF/Inputs/icf-merge3.s
new file mode 100644
index 00000000000..91bf05ebea2
--- /dev/null
+++ b/lld/test/ELF/Inputs/icf-merge3.s
@@ -0,0 +1,10 @@
+.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
diff --git a/lld/test/ELF/icf-merge-sec.s b/lld/test/ELF/icf-merge-sec.s
new file mode 100644
index 00000000000..39f6a884fa9
--- /dev/null
+++ b/lld/test/ELF/icf-merge-sec.s
@@ -0,0 +1,18 @@
+# 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
diff --git a/lld/test/ELF/icf-merge.s b/lld/test/ELF/icf-merge.s
new file mode 100644
index 00000000000..938b749da6b
--- /dev/null
+++ b/lld/test/ELF/icf-merge.s
@@ -0,0 +1,27 @@
+# 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