[lld-macho] ICF: Fold some sections with differing addends

[int3]

Summary

We previously treated all sections with differing addends as
unequal. This is not always true, particularly when the sections are
referencing literals: different addends may point to the same literal in
the output binary. References to absolute symbols and alt_entry symbols
can manifest this issue too (see icf.s), but are less common in practice.

To achieve this, we 1) move the addend check later in equalsConstant()
and 2) adjust our hash function to ignore symbol values and reloc
addends.

Along the way, I removed stubsHelperIndex from the hash computation as
it is effectively a no-op: Since D105044: [lld-macho] Move ICF earlier to avoid emitting redundant binds, ICF runs before
stubsHelperIndex gets set. The present implementation doesn't attempt
to factor DylibSymbol references into the hash at all, mirroring
LLD-ELF's approach. We may want to revisit this in the future after
doing some benchmarking.

[int3]

will put up a better approach

lld/MachO/ICF.cpp

auto f = [](const Reloc &ra, const Reloc &rb) {
     if (ra.type != rb.type)
       return false;
     if (ra.pcrel != rb.pcrel)
       return false;
     if (ra.length != rb.length)
       return false;
     if (ra.offset != rb.offset)
       return false;
-    if (ra.addend != rb.addend)
-      return false;
     if (ra.referent.is<Symbol *>() != rb.referent.is<Symbol *>())
       return false;
 
     InputSection *isecA, *isecB;
+    int64_t addA = ra.addend;
+    int64_t addB = rb.addend;
     if (ra.referent.is<Symbol *>()) {
       const auto *sa = ra.referent.get<Symbol *>();
       const auto *sb = rb.referent.get<Symbol *>();
       if (sa->kind() != sb->kind())
         return false;
       if (isa<Defined>(sa)) {
         const auto *da = cast<Defined>(sa);
         const auto *db = cast<Defined>(sb);
+        addA += da->value;
+        addB += db->value;
         if (da->isec && db->isec) {
           isecA = da->isec;
           isecB = db->isec;
         } else {
           assert(da->isAbsolute() && db->isAbsolute());
-          return da->value == db->value;
+          return addA == addB;
         }
       } else {
         assert(isa<DylibSymbol>(sa));
+        assert(addA == 0 && addB == 0);
         return sa == sb;
       }
     } else {
       isecA = ra.referent.get<InputSection *>();
       isecB = rb.referent.get<InputSection *>();
     }
 
     if (isecA->parent != isecB->parent)
       return false;
     // Sections with identical parents should be of the same kind.
     assert(isecA->kind() == isecB->kind());
     // We will compare ConcatInputSection contents in equalsVariable.
     if (isa<ConcatInputSection>(isecA))
-      return true;
+      return addA == addB;
     // Else we have two literal sections. References to them are equal iff their
     // offsets in the output section are equal.
-    return isecA->getOffset(ra.addend) == isecB->getOffset(rb.addend);
+    return isecA->getOffset(addA) == isecB->getOffset(addB);
   };
   return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
                     f);
 }
 
 // Compare the "moving" parts of two ConcatInputSections -- i.e. everything not
 // handled by equalsConstant().
 static bool equalsVariable(const ConcatInputSection *ia,

 }
 
 void ICF::run() {
   // Into each origin-section hash, combine all reloc referent section hashes.
   for (icfPass = 0; icfPass < 2; ++icfPass) {
     parallelForEach(icfInputs, [&](ConcatInputSection *isec) {
       uint64_t hash = isec->icfEqClass[icfPass % 2];
       for (const Reloc &r : isec->relocs) {
-        if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
-          if (auto *dylibSym = dyn_cast<DylibSymbol>(sym))
-            hash += dylibSym->stubsHelperIndex;
-          else if (auto *defined = dyn_cast<Defined>(sym)) {
-            if (defined->isec) {
-              if (auto isec = dyn_cast<ConcatInputSection>(defined->isec))
-                hash += defined->value + isec->icfEqClass[icfPass % 2];
-              else
-                hash += defined->isec->kind() +
-                        defined->isec->getOffset(defined->value);
-            } else {
-              hash += defined->value;
-            }
-          } else
-            llvm_unreachable("foldIdenticalSections symbol kind");
-        }
+        if (auto *sym = r.referent.dyn_cast<Symbol *>())
+          if (auto *defined = dyn_cast<Defined>(sym))
+            if (auto isec = dyn_cast_or_null<ConcatInputSection>(defined->isec))
+              hash += isec->icfEqClass[icfPass % 2];
       }
       // Set MSB to 1 to avoid collisions with non-hashed classes.
       isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 63);
     });
   }
 
   llvm::stable_sort(
       icfInputs, [](const ConcatInputSection *a, const ConcatInputSection *b) {

lld/test/MachO/icf-literals.s

 # REQUIRES: x86
 # RUN: rm -rf %t; mkdir %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t/test.o
 # RUN: %lld -lSystem --icf=all -o %t/test %t/test.o
 # RUN: llvm-objdump --macho --syms -d %t/test | FileCheck %s
 
 # CHECK:      _main:
 # CHECK-NEXT: callq   _foo2_ref
 # CHECK-NEXT: callq   _foo2_ref
+# CHECK-NEXT: callq   _lfoo2_ref
+# CHECK-NEXT: callq   _lfoo2_ref
 # CHECK-NEXT: callq   _bar2_ref
 # CHECK-NEXT: callq   _bar2_ref
 # CHECK-NEXT: callq   _baz2_ref
 # CHECK-NEXT: callq   _baz2_ref
 # CHECK-NEXT: callq   _qux2_ref
 # CHECK-NEXT: callq   _qux2_ref
+# CHECK-NEXT: callq   _lqux2_ref
+# CHECK-NEXT: callq   _lqux2_ref
 
-# CHECK:      [[#%.16x,FOO:]]     l     O __TEXT,__cstring _foo1
-# CHECK-NEXT: [[#%.16x,FOO:]]     l     O __TEXT,__cstring _foo2
-# CHECK-NEXT: [[#%.16x,BAR:]]     l     O __TEXT,__cstring _bar1
-# CHECK-NEXT: [[#%.16x,BAR:]]     l     O __TEXT,__cstring _bar2
-# CHECK-NEXT: [[#%.16x,BAZ:]]     l     O __TEXT,__literals _baz1
-# CHECK-NEXT: [[#%.16x,BAZ:]]     l     O __TEXT,__literals _baz2
-# CHECK-NEXT: [[#%.16x,QUX:]]     l     O __TEXT,__literals _qux1
-# CHECK-NEXT: [[#%.16x,QUX:]]     l     O __TEXT,__literals _qux2
-# CHECK-NEXT: [[#%.16x,FOO_REF:]] l     F __TEXT,__text _foo1_ref
-# CHECK-NEXT: [[#%.16x,FOO_REF:]] l     F __TEXT,__text _foo2_ref
-# CHECK-NEXT: [[#%.16x,BAR_REF:]] l     F __TEXT,__text _bar1_ref
-# CHECK-NEXT: [[#%.16x,BAR_REF:]] l     F __TEXT,__text _bar2_ref
-# CHECK-NEXT: [[#%.16x,BAZ_REF:]] l     F __TEXT,__text _baz1_ref
-# CHECK-NEXT: [[#%.16x,BAZ_REF:]] l     F __TEXT,__text _baz2_ref
-# CHECK-NEXT: [[#%.16x,QUX_REF:]] l     F __TEXT,__text _qux1_ref
-# CHECK-NEXT: [[#%.16x,QUX_REF:]] l     F __TEXT,__text _qux2_ref
+# CHECK:      [[#%.16x,FOO:]]      l     O __TEXT,__cstring _foo1
+# CHECK-NEXT: [[#%.16x,FOO:]]      l     O __TEXT,__cstring _foo2
+# CHECK-NEXT: [[#%.16x,BAR:]]      l     O __TEXT,__cstring _bar1
+# CHECK-NEXT: [[#%.16x,BAR:]]      l     O __TEXT,__cstring _bar2
+# CHECK-NEXT: [[#%.16x,BAZ:]]      l     O __TEXT,__literals _baz1
+# CHECK-NEXT: [[#%.16x,BAZ:]]      l     O __TEXT,__literals _baz2
+# CHECK-NEXT: [[#%.16x,QUX:]]      l     O __TEXT,__literals _qux1
+# CHECK-NEXT: [[#%.16x,QUX:]]      l     O __TEXT,__literals _qux2
+# CHECK-NEXT: [[#%.16x,FOO_REF:]]  l     F __TEXT,__text _foo1_ref
+# CHECK-NEXT: [[#%.16x,FOO_REF:]]  l     F __TEXT,__text _foo2_ref
+# CHECK-NEXT: [[#%.16x,LFOO_REF:]] l     F __TEXT,__text _lfoo1_ref
+# CHECK-NEXT: [[#%.16x,LFOO_REF:]] l     F __TEXT,__text _lfoo2_ref
+# CHECK-NEXT: [[#%.16x,BAR_REF:]]  l     F __TEXT,__text _bar1_ref
+# CHECK-NEXT: [[#%.16x,BAR_REF:]]  l     F __TEXT,__text _bar2_ref
+# CHECK-NEXT: [[#%.16x,BAZ_REF:]]  l     F __TEXT,__text _baz1_ref
+# CHECK-NEXT: [[#%.16x,BAZ_REF:]]  l     F __TEXT,__text _baz2_ref
+# CHECK-NEXT: [[#%.16x,QUX_REF:]]  l     F __TEXT,__text _qux1_ref
+# CHECK-NEXT: [[#%.16x,QUX_REF:]]  l     F __TEXT,__text _qux2_ref
+# CHECK-NEXT: [[#%.16x,LQUX_REF:]] l     F __TEXT,__text _lqux1_ref
+# CHECK-NEXT: [[#%.16x,LQUX_REF:]] l     F __TEXT,__text _lqux2_ref
 
 ## _foo1 vs _bar1: same section, different offsets
 ## _foo1 vs _baz1: same offset, different sections
+## Lfoo*, Lqux*: different embedded addends pointing to the same content
 
 .cstring
 _foo1:
   .asciz "foo"
 _foo2:
   .asciz "foo"
+Lfoo1:
+  .asciz "foo"
+Lfoo2:
+  .asciz "foo"
 _bar1:
   .asciz "bar"
 _bar2:
   .asciz "bar"
 
 .literal8
 _baz1:
   .quad 0xdead
 _baz2:
   .quad 0xdead
 _qux1:
   .quad 0xbeef
 _qux2:
   .quad 0xbeef
+Lqux1:
+  .quad 0xbeef
+Lqux2:
+  .quad 0xbeef
 
 .text
 _foo1_ref:
-  mov _foo1@GOTPCREL(%rip), %rax
+  mov _foo1(%rip), %rax
 _foo2_ref:
-  mov _foo2@GOTPCREL(%rip), %rax
+  mov _foo2(%rip), %rax
+_lfoo1_ref:
+  mov Lfoo1(%rip), %rax
+_lfoo2_ref:
+  mov Lfoo2(%rip), %rax
 _bar1_ref:
-  mov _bar1@GOTPCREL(%rip), %rax
+  mov _bar1(%rip), %rax
 _bar2_ref:
-  mov _bar2@GOTPCREL(%rip), %rax
+  mov _bar2(%rip), %rax
 _baz1_ref:
-  mov _baz1@GOTPCREL(%rip), %rax
+  mov _baz1(%rip), %rax
 _baz2_ref:
-  mov _baz2@GOTPCREL(%rip), %rax
+  mov _baz2(%rip), %rax
 _qux1_ref:
-  mov _qux1@GOTPCREL(%rip), %rax
+  mov _qux1(%rip), %rax
 _qux2_ref:
-  mov _qux2@GOTPCREL(%rip), %rax
+  mov _qux2(%rip), %rax
+_lqux1_ref:
+  mov Lqux1(%rip), %rax
+_lqux2_ref:
+  mov Lqux2(%rip), %rax
 
 .globl _main
 _main:
   callq _foo1_ref
   callq _foo2_ref
+  callq _lfoo1_ref
+  callq _lfoo2_ref
   callq _bar1_ref
   callq _bar2_ref
   callq _baz1_ref
   callq _baz2_ref
   callq _qux1_ref
   callq _qux2_ref
+  callq _lqux1_ref
+  callq _lqux2_ref
 
 .subsections_via_symbols

lld/test/MachO/icf.s

 # REQUIRES: x86
 # RUN: rm -rf %t; split-file %s %t
 
 ## Check that we fold identical function bodies correctly. Note: This test
 ## has many different functions; each group of similarly-named functions aim
 ## to test one aspect of ICF's logic. To prevent accidental folding across
 ## groups, we use `mov` instructions with a variety of immediates, with
 ## different immediate values for each group.
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %t/main.s -o %t/main.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %t/abs.s -o %t/abs.o
 # RUN: %lld -lSystem --icf=all -o %t/main %t/main.o %t/abs.o
 # RUN: llvm-objdump -d --syms %t/main | FileCheck %s
 
 # CHECK-LABEL: SYMBOL TABLE:
-# CHECK: [[#%x,ABS1B_REF:]]                 l     F __TEXT,__text _abs1a_ref
-# CHECK: [[#%x,ABS1B_REF:]]                 l     F __TEXT,__text _abs1b_ref
+# CHECK: [[#%x,ABS1C_REF:]]                 l     F __TEXT,__text _abs1a_ref
+# CHECK: [[#%x,ABS1C_REF:]]                 l     F __TEXT,__text _abs1b_ref
+# CHECK: [[#%x,ABS1C_REF:]]                 l     F __TEXT,__text _abs1c_ref
 # CHECK: [[#%x,ABS1B_REF_WITH_ADDEND:]]     l     F __TEXT,__text _abs1a_ref_with_addend
 # CHECK: [[#%x,ABS1B_REF_WITH_ADDEND:]]     l     F __TEXT,__text _abs1b_ref_with_addend
 # CHECK: [[#%x,ABS2_REF:]]                  l     F __TEXT,__text _abs2_ref
 # CHECK: [[#%x,NOT_ABS_REF:]]               l     F __TEXT,__text _not_abs_ref
 # CHECK: [[#%x,DYLIB_REF_2:]]               l     F __TEXT,__text _dylib_ref_1
 # CHECK: [[#%x,DYLIB_REF_2:]]               l     F __TEXT,__text _dylib_ref_2
 # CHECK: [[#%x,DYLIB_REF_3:]]               l     F __TEXT,__text _dylib_ref_3
 # CHECK: [[#%x,ALT:]]                       l     F __TEXT,__text _alt
 # CHECK: [[#%x,WITH_ALT_ENTRY:]]            l     F __TEXT,__text _with_alt_entry
 # CHECK: [[#%x,WITH_ALT_ENTRY:]]            l     F __TEXT,__text _no_alt_entry
-# CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_2:]] l     F __TEXT,__text _defined_ref_with_addend_1
-# CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_2:]] l     F __TEXT,__text _defined_ref_with_addend_2
+# CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_3:]] l     F __TEXT,__text _defined_ref_with_addend_1
+# CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_3:]] l     F __TEXT,__text _defined_ref_with_addend_2
+# CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_3:]] l     F __TEXT,__text _defined_ref_with_addend_3
 # CHECK: [[#%x,RECURSIVE:]]                 l     F __TEXT,__text _recursive
 # CHECK: [[#%x,CALL_RECURSIVE_2:]]          l     F __TEXT,__text _call_recursive_1
 # CHECK: [[#%x,CALL_RECURSIVE_2:]]          l     F __TEXT,__text _call_recursive_2
 # CHECK: [[#%x,CHECK_LENGTH_1:]]            l     F __TEXT,__text _check_length_1
 # CHECK: [[#%x,CHECK_LENGTH_2:]]            l     F __TEXT,__text _check_length_2
 # CHECK: [[#%x,HAS_UNWIND_1:]]              l     F __TEXT,__text _has_unwind_1
 # CHECK: [[#%x,HAS_UNWIND_2:]]              l     F __TEXT,__text _has_unwind_2
 # CHECK: [[#%x,MR2:]]                       l     F __TEXT,__text _mr1
 # CHECK: [[#%x,MR2:]]                       l     F __TEXT,__text _mr2
 # CHECK: [[#%x,INIT_2:]]                    l     F __TEXT,__text _init_1
 # CHECK: [[#%x,INIT_2:]]                    l     F __TEXT,__text _init_2
 # CHECK: [[#%x,INIT_3:]]                    l     O __TEXT,__foo  _init_3
 ### FIXME: Mutually-recursive functions with identical bodies (see below)
 # COM:   [[#%x,XR:]]                        g   F __TEXT,__text _xr1
 # COM:   [[#%x,XR]]                         g   F __TEXT,__text _xr2
 
 # CHECK-LABEL: Disassembly of section __TEXT,__text:
 # CHECK:        <_main>:
-# CHECK: callq  0x[[#%x,ABS1B_REF:]]                 <_abs1b_ref>
-# CHECK: callq  0x[[#%x,ABS1B_REF:]]                 <_abs1b_ref>
+# CHECK: callq  0x[[#%x,ABS1C_REF:]]                 <_abs1c_ref>
+# CHECK: callq  0x[[#%x,ABS1C_REF:]]                 <_abs1c_ref>
+# CHECK: callq  0x[[#%x,ABS1C_REF:]]                 <_abs1c_ref>
 # CHECK: callq  0x[[#%x,ABS1B_REF_WITH_ADDEND:]]     <_abs1b_ref_with_addend>
 # CHECK: callq  0x[[#%x,ABS1B_REF_WITH_ADDEND:]]     <_abs1b_ref_with_addend>
 # CHECK: callq  0x[[#%x,ABS2_REF:]]                  <_abs2_ref>
 # CHECK: callq  0x[[#%x,NOT_ABS_REF:]]               <_not_abs_ref>
 # CHECK: callq  0x[[#%x,DYLIB_REF_2:]]               <_dylib_ref_2>
 # CHECK: callq  0x[[#%x,DYLIB_REF_2:]]               <_dylib_ref_2>
 # CHECK: callq  0x[[#%x,DYLIB_REF_3:]]               <_dylib_ref_3>
 # CHECK: callq  0x[[#%x,ALT:]]                       <_alt>

 ### TODO:
 ### * Fold: funcs only differ in alignment
 ### * No fold: func is weak? preemptable?
 ### * Test that we hash things appropriately w/ minimal collisions
 
 #--- abs.s
 .subsections_via_symbols
 
-.globl _abs1a, _abs1b, _abs2, _not_abs
+.globl _abs1a, _abs1b, _abs1c, _abs2, _not_abs
 _abs1a = 0xfac3
 _abs1b = 0xfac3
+_abs1c = 0xfac2
 _abs2 =  0xf00d
 
 .data
 .space 0xfac3
 ## _not_abs has the same Defined::value as _abs1{a,b}
 _not_abs:
 
 #--- main.s
 .subsections_via_symbols
 .text
 
 _abs1a_ref:
   movabs $_abs1a, %rdx
 
 _abs1b_ref:
   movabs $_abs1b, %rdx
 
+_abs1c_ref:
+  movabs $_abs1c + 1, %rdx
+
 _abs1a_ref_with_addend:
   movabs $_abs1a + 3, %rdx
 
 _abs1b_ref_with_addend:
   movabs $_abs1b + 3, %rdx
 
 ## No fold: the absolute symbol value differs
 _abs2_ref:
_no_alt_entry:
   ret
 
 _defined_ref_with_addend_1:
   callq _with_alt_entry + 4
 
 _defined_ref_with_addend_2:
   callq _with_alt_entry + 4
 
+_defined_ref_with_addend_3:
+  callq _alt + 14 ## same address as _with_alt_entry + 4
+
 ## _recursive has the same body as its next two callers, but cannot be folded
 ## with them.
 _recursive:
   callq _recursive
 
 _call_recursive_1:
   callq _recursive
 

 _init_3:
   movq $12938, %rax
 
 .text
 .globl _main
 _main:
   callq _abs1a_ref
   callq _abs1b_ref
+  callq _abs1c_ref
   callq _abs1a_ref_with_addend
   callq _abs1b_ref_with_addend
   callq _abs2_ref
   callq _not_abs_ref
   callq _dylib_ref_1
   callq _dylib_ref_2
   callq _dylib_ref_3
   callq _alt
   callq _with_alt_entry
   callq _no_alt_entry
   callq _defined_ref_with_addend_1
   callq _defined_ref_with_addend_2
+  callq _defined_ref_with_addend_3
   callq _recursive
   callq _call_recursive_1
   callq _call_recursive_2
   callq _check_length_1
   callq _check_length_2
   callq _has_unwind_1
   callq _has_unwind_2
   callq _mr1
   callq _mr2
   callq _xr1
   callq _xr2
   callq _init_1
   callq _init_2
   callq _init_3