[lld-macho] Deduplicate CFStrings during ICF

[int3]

Summary

__cfstring has embedded addends that foil ICF's hashing / equality
checks. (We can ignore embedded addends when doing ICF because the same
information gets recorded in our Reloc structs.) Therefore, in order to
properly dedup CFStrings, we create a mutable copy of the CFString and
zero out the embedded addends before performing any hashing / equality
checks.

(We did in fact have a partial implementation of CFString deduplication
already. However, it only worked when the cstrings they point to are at
identical offsets in their object files.)

I anticipate this approach can be extended to other similar
statically-allocated struct sections in the future.

In addition, we previously treated all references with differing addends
as unequal. This is not true when the references are to literals:
different addends may point to the same literal in the output binary. In
particular, __cfstring has such references to __cstring. I've
adjusted ICF's equalsConstant logic accordingly, and I've added a few
more tests to make sure the addend-comparison code path is adequately
covered.

Fixes https://github.com/llvm/llvm-project/issues/51281.

[int3]

update

[Roger]

As I understand, we are zero-ing out the addends of all cfstring sections because we are moving the addend check from the section comparisons to the relocation comparisons. All relocation comparisons (not just those for cfsections) will now check addend equality. LGTM

lld/MachO/ICF.cpp

129

For the Undefined case, it looks like we're making a functional change from returning sa == sb to always returning false. Was the previous behavior a bug? Is this Undefined symbol a symbol that needs to be linked to a definition in another source file?

[int3]

lld/MachO/ICF.cpp

129

oops, no, the previous behavior was intended. Let me fix this and add a test so we don't regress

[int3]

update

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;
 
     uint64_t valueA = 0;
     uint64_t valueB = 0;
     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)) {
-        // ICF runs before Undefineds are reported.
-        assert(isa<DylibSymbol>(sa) || isa<Undefined>(sa));
-        return sa == sb;
-      }
+      // ICF runs before Undefineds are treated (and potentially converted into
+      // DylibSymbols).
+      if (isa<DylibSymbol>(sa) || isa<Undefined>(sa))
+        return sa == sb && ra.addend == rb.addend;
+      assert(isa<Defined>(sa));
       const auto *da = cast<Defined>(sa);
       const auto *db = cast<Defined>(sb);
       if (!da->isec || !db->isec) {
         assert(da->isAbsolute() && db->isAbsolute());
-        return da->value == db->value;
+        return da->value + ra.addend == db->value + rb.addend;
       }
       isecA = da->isec;
       valueA = da->value;
       isecB = db->isec;
       valueB = db->value;
     } 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 ra.addend == rb.addend;
     // Else we have two literal sections. References to them are equal iff their
     // offsets in the output section are equal.
     return isecA->getOffset(valueA + ra.addend) ==
            isecB->getOffset(valueB + rb.addend);
   };
   return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
                     f);
 }
if (isHashable) {
       for (Defined *d : isec->symbols)
         if (d->unwindEntry)
           hashable.push_back(d->unwindEntry);
     } else {
       isec->icfEqClass[0] = ++icfUniqueID;
     }
   }
   parallelForEach(hashable, [](ConcatInputSection *isec) {
+    // __cfstring has embedded addends that foil ICF's hashing / equality
+    // checks. (We can ignore embedded addends when doing ICF because the same
+    // information gets recorded in our Reloc structs.) We therefore create a
+    // mutable copy of the CFString and zero out the embedded addends before
+    // performing any hashing / equality checks.
+    if (isCfStringSection(isec)) {
+      MutableArrayRef<uint8_t> copy = isec->data.copy(bAlloc());
+      for (const Reloc &r : isec->relocs)
+        target->relocateOne(copy.data() + r.offset, r, /*va=*/0, /*relocVA=*/0);
+      isec->data = copy;
+    }
     assert(isec->icfEqClass[0] == 0); // don't overwrite a unique ID!
     // Turn-on the top bit to guarantee that valid hashes have no collisions
     // with the small-integer unique IDs for ICF-ineligible sections
     isec->icfEqClass[0] = xxHash64(isec->data) | (1ull << 31);
   });
   // Now that every input section is either hashed or marked as unique, run the
   // segregation algorithm to detect foldable subsections.
   ICF(hashable).run();
 }

lld/test/MachO/cfstring-dedup.s

 # CHECK-NEXT:  segment      section      address  type       addend dylib            symbol
 # CHECK-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer         0 CoreFoundation   ___CFConstantStringClassReference
 # CHECK-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer         0 CoreFoundation   ___CFConstantStringClassReference
 # CHECK-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer         0 CoreFoundation   ___CFConstantStringClassReference
 # CHECK-EMPTY:
 
 #--- foo1.s
 .cstring
+L_.str.0:
+  .asciz  "bar"
+## This string is at a different offset than the corresponding "foo" string in
+## foo2.s. Make sure that we treat references to either string as equivalent.
 L_.str:
   .asciz  "foo"
 
 .section  __DATA,__cfstring
 .p2align  3
 L__unnamed_cfstring_:
   .quad  ___CFConstantStringClassReference
   .long  1992 ## utf-8
   .space  4
   .quad  L_.str
   .quad  3 ## strlen
 
 _named_cfstring:
   .quad  ___CFConstantStringClassReference
   .long  1992 ## utf-8
   .space  4
   .quad  L_.str
   .quad  3 ## strlen
 
 .section  __TEXT,__ustring
-l_.str.2:
+l_.ustr:
   .short  102 ## f
   .short  111 ## o
   .short  0   ## \0
   .short  111 ## o
   .short  0   ## \0
 
 ## FIXME: We should be able to deduplicate UTF-16 CFStrings too.
 ## Note that this string contains a null byte in the middle -- any dedup code
 ## we add should take care to handle this correctly.
 ## Technically, UTF-8 should support encoding null bytes too, but since we
 ## atomize the __cstring section at every null byte, this isn't supported. ld64
 ## doesn't support it either, and clang seems to always emit a UTF-16 CFString
 ## if it needs to contain a null, so I think we're good here.
 .section  __DATA,__cfstring
 .p2align  3
 L__unnamed_cfstring_.2:
   .quad  ___CFConstantStringClassReference
   .long  2000 ## utf-16
   .space  4
-  .quad  l_.str.2
+  .quad  l_.ustr
   .quad  4 ## strlen
 
 .text
 .globl  _foo1, _foo1_utf16, _named_foo1
 _foo1:
   movq L__unnamed_cfstring_(%rip), %rax
 
 _foo1_utf16:
_named_cfstring:
   .quad  ___CFConstantStringClassReference
   .long  1992 ## utf-8
   .space  4
   .quad  L_.str
   .quad  3 ## strlen
 
 .section  __TEXT,__ustring
   .p2align  1
-l_.str.2:
+l_.ustr:
   .short  102 ## f
   .short  111 ## o
   .short  0   ## \0
   .short  111 ## o
   .short  0   ## \0
 
 .section  __DATA,__cfstring
 .p2align  3
 L__unnamed_cfstring_.2:
   .quad  ___CFConstantStringClassReference
   .long  2000 ## utf-16
   .space  4
-  .quad  l_.str.2
+  .quad  l_.ustr
   .quad  4 ## strlen
 
 .text
 .globl  _foo2, _foo2_utf16, _named_foo2
 _foo2:
   movq L__unnamed_cfstring_(%rip), %rax
 
 _foo2_utf16:
   movq L__unnamed_cfstring_.2(%rip), %rax
 
 _named_foo2:
   movq _named_cfstring(%rip), %rax
 
 .subsections_via_symbols

lld/test/MachO/icf-undef.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %t/test.s -o %t/test.o
+
+## Check that we correctly dedup sections that reference dynamic-lookup symbols.
+# RUN: %lld -lSystem -dylib --icf=all -undefined dynamic_lookup -o %t/test %t/test.o
+# RUN: llvm-objdump --macho --syms %t/test | FileCheck %s
+
+## Check that we still raise an error when using regular undefined symbol
+## treatment.
+# RUN: not %lld -lSystem -dylib --icf=all -o /dev/null %t/test.o 2>&1 | \
+# RUN:   FileCheck %s --check-prefix=ERR
+
+# CHECK: [[#%x,ADDR:]] l    F __TEXT,__text _foo
+# CHECK: [[#ADDR]]     l    F __TEXT,__text _bar
+
+# ERR: error: undefined symbol: _undef
+
+#--- test.s
+
+.subsections_via_symbols
+
+_foo:
+  callq _undef + 1
+
+_bar:
+  callq _undef + 1

lld/test/MachO/icf.s

 # CHECK: [[#%x,ABS1B_REF:]]                 l     F __TEXT,__text _abs1b_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,DYLIB_REF_4:]]               l     F __TEXT,__text _dylib_ref_4
 # 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_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_2:]]              l     F __TEXT,__text _has_unwind_1
 # CHECK: [[#%x,HAS_UNWIND_2:]]              l     F __TEXT,__text _has_unwind_2
 # CHECK: [[#%x,HAS_UNWIND_3:]]              l     F __TEXT,__text _has_unwind_3

 # CHECK: callq 0x[[#%x,ABS1B_REF:]]                 <_abs1b_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,DYLIB_REF_4:]]               <_dylib_ref_4>
 # CHECK: callq 0x[[#%x,ALT:]]                       <_alt>
 # CHECK: callq 0x[[#%x,WITH_ALT_ENTRY:]]            <_with_alt_entry>
 # CHECK: callq 0x[[#%x,WITH_ALT_ENTRY:]]            <_with_alt_entry>
 # CHECK: callq 0x[[#%x,DEFINED_REF_WITH_ADDEND_2:]] <_defined_ref_with_addend_2>
 # CHECK: callq 0x[[#%x,DEFINED_REF_WITH_ADDEND_2:]] <_defined_ref_with_addend_2>
+# CHECK: callq 0x[[#%x,DEFINED_REF_WITH_ADDEND_3:]] <_defined_ref_with_addend_3>
 # CHECK: callq 0x[[#%x,RECURSIVE:]]                 <_recursive>
 # CHECK: callq 0x[[#%x,CALL_RECURSIVE_2:]]          <_call_recursive_2>
 # CHECK: callq 0x[[#%x,CALL_RECURSIVE_2:]]          <_call_recursive_2>
 # CHECK: callq 0x[[#%x,CHECK_LENGTH_1:]]            <_check_length_1>
 # CHECK: callq 0x[[#%x,CHECK_LENGTH_2:]]            <_check_length_2>
 # CHECK: callq 0x[[#%x,HAS_UNWIND_2:]]              <_has_unwind_2>
 # CHECK: callq 0x[[#%x,HAS_UNWIND_2:]]              <_has_unwind_2>
 # CHECK: callq 0x[[#%x,HAS_UNWIND_3:]]              <_has_unwind_3>
_dylib_ref_2:
   mov ___nan@GOTPCREL(%rip), %rax
   callq ___isnan
 
 ## No fold: referent dylib symbol differs
 _dylib_ref_3:
   mov ___inf@GOTPCREL(%rip), %rax
   callq ___inf
 
+## No fold: referent dylib addend differs
+_dylib_ref_4:
+  mov ___nan + 1@GOTPCREL(%rip), %rax
+  callq ___inf + 1
+
 ## We can merge two sections even if one of them has an alt entry. Just make
 ## sure we don't merge the alt entry symbol with a regular symbol.
 .alt_entry _alt
 _with_alt_entry:
   movq $3132, %rax
 _alt:
   ret
 
 _no_alt_entry:
   movq $3132, %rax
   ret
 
 _defined_ref_with_addend_1:
   callq _with_alt_entry + 4
 
 _defined_ref_with_addend_2:
   callq _with_alt_entry + 4
 
+# No fold: addend differs
+_defined_ref_with_addend_3:
+  callq _with_alt_entry + 8
+
 ## _recursive has the same body as its next two callers, but cannot be folded
 ## with them.
 _recursive:
   callq _recursive
 
 _call_recursive_1:
   callq _recursive
 
_main:
   callq _abs1b_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 _dylib_ref_4
   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 _has_unwind_3
   callq _mutually_recursive_1
   callq _mutually_recursive_2
   callq _asymmetric_recursive_1
   callq _asymmetric_recursive_2
   callq _init_1
   callq _init_2
   callq _init_3