[lld-macho] Have ICF dedup explicitly-defined selrefs

[int3]

Summary

This is what ld64 does (though it doesn't use ICF to do this; instead it
always dedups selrefs by default).

We'll want to dedup implicitly-defined selrefs as well, but I will leave
that for future work.

Additionally, I'm not *super* happy with the current LLD implementation
because I think it is rather janky and inefficient. But at least it
moves us toward the goal of closing the size gap with ld64. I've
described ideas for cleaning up our implementation here:
https://github.com/llvm/llvm-project/issues/57714

[int3]

lld/MachO/ICF.cpp

414

hm I should rename this to foldable too

[Roger]

lld/MachO/ICF.cpp

414

Agreed :)

417–423

I really appreciate pulling out these boolean expressions into their own variables to give a name to what they represent. If it can be done any further, I'd really encourage it :)

[thakis]

Out of curiosity, do you have any numbers on what that does to the size gap for your apps?

lld/MachO/ICF.cpp

417–423

+1, but maybe some of that could land in a separate (unreviewed, behavior-preserving) commit so it's easier to see the behavior change in this diff :)

[int3]

lld/MachO/ICF.cpp

417–423

split them out into https://github.com/llvm/llvm-project/commit/8d4ca09d068d66d13b258ebccdb9470b50fff881 :)

[int3]

Out of curiosity, do you have any numbers on what that does to the size gap for your apps?

I'll re-gather some numbers in a bit. But this is basically the last of the non-__text sections for us that showed a significant size regression wrt ld64's output.

lld/MachO/ICF.cpp

void macho::foldIdenticalSections(bool onlyCfStrings) {
 
   // If an InputSection is ineligible for ICF, we give it a unique ID to force
   // it into an unfoldable singleton equivalence class.  Begin the unique-ID
   // space at inputSections.size(), so that it will never intersect with
   // equivalence-class IDs which begin at 0. Since hashes & unique IDs never
   // coexist with equivalence-class IDs, this is not necessary, but might help
   // someone keep the numbers straight in case we ever need to debug the
   // ICF::segregate()
   std::vector<ConcatInputSection *> foldable;
   uint64_t icfUniqueID = inputSections.size();
   for (ConcatInputSection *isec : inputSections) {
-    bool isFoldableWithAddendsRemoved =
-        isCfStringSection(isec) || isClassRefsSection(isec);
+    bool isFoldableWithAddendsRemoved = isCfStringSection(isec) ||
+                                        isClassRefsSection(isec) ||
+                                        isSelRefsSection(isec);
+    // NOTE: __objc_selrefs is typically marked as no_dead_strip by MC, but we
+    // can still fold it.
+    bool hasFoldableFlags = (isSelRefsSection(isec) ||
+                             sectionType(isec->getFlags()) == MachO::S_REGULAR);
     // FIXME: consider non-code __text sections as foldable?
     bool isFoldable = (!onlyCfStrings || isCfStringSection(isec)) &&
-                      (isCodeSection(isec) || isGccExceptTabSection(isec) ||
-                       isFoldableWithAddendsRemoved) &&
+                      (isCodeSection(isec) || isFoldableWithAddendsRemoved ||
+                       isGccExceptTabSection(isec)) &&
                       !isec->keepUnique && !isec->shouldOmitFromOutput() &&
-                      sectionType(isec->getFlags()) == MachO::S_REGULAR;
+                      hasFoldableFlags;
     if (isFoldable) {
       foldable.push_back(isec);
       for (Defined *d : isec->symbols)
         if (d->unwindEntry)
           foldable.push_back(d->unwindEntry);
 
-      // __cfstring has embedded addends that foil ICF's hashing / equality
+      // Some sections have 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.
+      // mutable copy of the the section data and zero out the embedded addends
+      // before performing any hashing / equality checks.
       if (isFoldableWithAddendsRemoved) {
         // We have to do this copying serially as the BumpPtrAllocator is not
         // thread-safe. FIXME: Make a thread-safe allocator.
         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;
       }
     } else if (!isEhFrameSection(isec)) {
-      // EH frames are gathered as foldable from unwindEntry above; give a
+      // EH frames are gathered as foldables from unwindEntry above; give a
       // unique ID to everything else.
       isec->icfEqClass[0] = ++icfUniqueID;
     }
   }
   parallelForEach(foldable, [](ConcatInputSection *isec) {
     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(foldable).run();
 }

lld/MachO/InputFiles.cpp

static Optional<size_t> getRecordSize(StringRef segname, StringRef name) {
   if (name == section_names::cfString && segname == segment_names::data)
     return target->wordSize == 8 ? 32 : 16;
 
   if (config->icfLevel == ICFLevel::none)
     return {};
 
   if (name == section_names::objcClassRefs && segname == segment_names::data)
     return target->wordSize;
+
+  if (name == section_names::objcSelrefs && segname == segment_names::data)
+    return target->wordSize;
   return {};
 }
 
 static Error parseCallGraph(ArrayRef<uint8_t> data,
                             std::vector<CallGraphEntry> &callGraph) {
   TimeTraceScope timeScope("Parsing call graph section");
   BinaryStreamReader reader(data, support::little);
   while (!reader.empty()) {

lld/MachO/InputSection.h

inline bool isWordLiteralSection(uint32_t flags) {
   return sectionType(flags) == llvm::MachO::S_4BYTE_LITERALS ||
          sectionType(flags) == llvm::MachO::S_8BYTE_LITERALS ||
          sectionType(flags) == llvm::MachO::S_16BYTE_LITERALS;
 }
 
 bool isCodeSection(const InputSection *);
 bool isCfStringSection(const InputSection *);
 bool isClassRefsSection(const InputSection *);
+bool isSelRefsSection(const InputSection *);
 bool isEhFrameSection(const InputSection *);
 bool isGccExceptTabSection(const InputSection *);
 
 extern std::vector<ConcatInputSection *> inputSections;
 
 namespace section_names {
 
 constexpr const char authGot[] = "__auth_got";

lld/MachO/InputSection.cpp

return isec->getName() == section_names::cfString &&
          isec->getSegName() == segment_names::data;
 }
 
 bool macho::isClassRefsSection(const InputSection *isec) {
   return isec->getName() == section_names::objcClassRefs &&
          isec->getSegName() == segment_names::data;
 }
 
+bool macho::isSelRefsSection(const InputSection *isec) {
+  return isec->getName() == section_names::objcSelrefs &&
+         isec->getSegName() == segment_names::data;
+}
+
 bool macho::isEhFrameSection(const InputSection *isec) {
   return isec->getName() == section_names::ehFrame &&
          isec->getSegName() == segment_names::text;
 }
 
 bool macho::isGccExceptTabSection(const InputSection *isec) {
   return isec->getName() == section_names::gccExceptTab &&
          isec->getSegName() == segment_names::text;
 }
 
 std::string lld::toString(const InputSection *isec) {
   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
 }

lld/test/MachO/objc-selrefs.s

 # REQUIRES: aarch64
 # RUN: rm -rf %t; split-file %s %t
 
-# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/existing.s -o %t/existing.o
-# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/main.s -o %t/main.o
-
-# RUN: %lld -arch arm64 -lSystem -o %t/out %t/existing.o %t/main.o
-# RUN: llvm-otool -vs __DATA __objc_selrefs %t/out | FileCheck %s --check-prefix=SELREFS
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/explicit-selrefs-1.s -o %t/explicit-selrefs-1.o
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/explicit-selrefs-2.s -o %t/explicit-selrefs-2.o
+# RUN: llvm-mc -filetype=obj -triple=arm64-apple-darwin %t/implicit-selrefs.s -o %t/implicit-selrefs.o
+
+# RUN: %lld -dylib -arch arm64 -lSystem -o %t/explicit-only-no-icf \
+# RUN:   %t/explicit-selrefs-1.o %t/explicit-selrefs-2.o
+# RUN: llvm-otool -vs __DATA __objc_selrefs %t/explicit-only-no-icf | \
+# RUN:   FileCheck %s --check-prefix=EXPLICIT-NO-ICF
+
+## NOTE: ld64 always dedups the selrefs unconditionally, but we only do it when
+## ICF is enabled.
+# RUN: %lld -dylib -arch arm64 -lSystem -o %t/explicit-only-with-icf \
+# RUN:   %t/explicit-selrefs-1.o %t/explicit-selrefs-2.o
+# RUN: llvm-otool -vs __DATA __objc_selrefs %t/explicit-only-with-icf \
+# RUN:   | FileCheck %s --check-prefix=EXPLICIT-WITH-ICF
 
 # SELREFS: Contents of (__DATA,__objc_selrefs) section
 # SELREFS-NEXT: __TEXT:__objc_methname:foo
 # SELREFS-NEXT: __TEXT:__objc_methname:bar
 # SELREFS-NEXT: __TEXT:__objc_methname:foo
 # SELREFS-NEXT: __TEXT:__objc_methname:length
 # SELREFS-EMPTY:
 
-# RUN: %lld -arch arm64 -lSystem -o %t/out %t/existing.o %t/main.o --deduplicate-literals
-# RUN: llvm-otool -vs __DATA __objc_selrefs %t/out | FileCheck %s --check-prefix=DEDUP
-
-# DEDUP: Contents of (__DATA,__objc_selrefs) section
-# DEDUP-NEXT: __TEXT:__objc_methname:foo
-# DEDUP-NEXT: __TEXT:__objc_methname:bar
+## We don't yet support dedup'ing implicitly-defined selrefs.
+# RUN: %lld -dylib -arch arm64 -lSystem --icf=all -o %t/explicit-and-implicit \
+# RUN:   %t/explicit-selrefs-1.o %t/explicit-selrefs-2.o %t/implicit-selrefs.o
+# RUN: llvm-otool -vs __DATA __objc_selrefs %t/explicit-and-implicit \
+# RUN:   | FileCheck %s --check-prefix=EXPLICIT-AND-IMPLICIT
+
+# EXPLICIT-NO-ICF:       Contents of (__DATA,__objc_selrefs) section
+# EXPLICIT-NO-ICF-NEXT:  __TEXT:__objc_methname:foo
+# EXPLICIT-NO-ICF-NEXT:  __TEXT:__objc_methname:bar
+# EXPLICIT-NO-ICF-NEXT:  __TEXT:__objc_methname:bar
+# EXPLICIT-NO-ICF-NEXT:  __TEXT:__objc_methname:foo
+
+# EXPLICIT-WITH-ICF:      Contents of (__DATA,__objc_selrefs) section
+# EXPLICIT-WITH-ICF-NEXT: __TEXT:__objc_methname:foo
+# EXPLICIT-WITH-ICF-NEXT: __TEXT:__objc_methname:bar
+
+# EXPLICIT-AND-IMPLICIT:      Contents of (__DATA,__objc_selrefs) section
+# EXPLICIT-AND-IMPLICIT-NEXT: __TEXT:__objc_methname:foo
+# EXPLICIT-AND-IMPLICIT-NEXT: __TEXT:__objc_methname:bar
 # NOTE: Ideally this wouldn't exist, but while it does it needs to point to the deduplicated string
-# DEDUP-NEXT: __TEXT:__objc_methname:foo
-# DEDUP-NEXT: __TEXT:__objc_methname:length
-# DEDUP-EMPTY:
+# EXPLICIT-AND-IMPLICIT-NEXT: __TEXT:__objc_methname:foo
+# EXPLICIT-AND-IMPLICIT-NEXT: __TEXT:__objc_methname:length
 
-#--- existing.s
+#--- explicit-selrefs-1.s
 .section  __TEXT,__objc_methname,cstring_literals
 lselref1:
   .asciz  "foo"
 lselref2:
   .asciz  "bar"
 
 .section  __DATA,__objc_selrefs,literal_pointers,no_dead_strip
 .p2align  3
   .quad lselref1
   .quad lselref2
+  .quad lselref2
+
+#--- explicit-selrefs-2.s
+.section  __TEXT,__objc_methname,cstring_literals
+lselref1:
+  .asciz  "foo"
+
+.section  __DATA,__objc_selrefs,literal_pointers,no_dead_strip
+.p2align  3
+  .quad lselref1
 
-#--- main.s
+#--- implicit-selrefs.s
 .text
 .globl _objc_msgSend
+.p2align 2
 _objc_msgSend:
   ret
 
-.globl _main
-_main:
-  bl  _objc_msgSend$length
-  bl  _objc_msgSend$foo
+.p2align 2
+_sender:
+  bl _objc_msgSend$length
+  bl _objc_msgSend$foo
   ret