[lld-macho] Deduplicate the `__objc_classrefs` section contents

[int3]

Summary

ld64 breaks down __objc_classrefs on a per-word level and deduplicates
them. This greatly reduces the number of bind entries emitted (and
therefore the amount of work dyld has to do at runtime). For
chromium_framework, this change to LLD cuts the number of (non-lazy)
binds from 912 to 190, getting us to parity with ld64 in this aspect.

[thakis]

lld/MachO/InputFiles.cpp

264

no else after return

[int3]

address comment

lld/MachO/ICF.cpp

void macho::foldIdenticalSections() {
   // 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 *> hashable;
   uint64_t icfUniqueID = inputSections.size();
   for (ConcatInputSection *isec : inputSections) {
     // FIXME: consider non-code __text sections as hashable?
-    bool isHashable = (isCodeSection(isec) || isCfStringSection(isec)) &&
+    bool isHashable = (isCodeSection(isec) || isCfStringSection(isec) ||
+                       isClassRefsSection(isec)) &&
                       !isec->shouldOmitFromOutput() &&
                       sectionType(isec->getFlags()) == MachO::S_REGULAR;
     if (isHashable) {
       hashable.push_back(isec);
       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)) {
+    if (isCfStringSection(isec) || isClassRefsSection(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/MachO/InputFiles.cpp

 // Some sections comprise of fixed-size records, so instead of splitting them at
 // symbol boundaries, we split them based on size. Records are distinct from
 // literals in that they may contain references to other sections, instead of
 // being leaf nodes in the InputSection graph.
 //
 // Note that "record" is a term I came up with. In contrast, "literal" is a term
 // used by the Mach-O format.
 static Optional<size_t> getRecordSize(StringRef segname, StringRef name) {
-  if (name == section_names::cfString) {
-    if (config->icfLevel != ICFLevel::none && segname == segment_names::data)
-      return target->wordSize == 8 ? 32 : 16;
-  } else if (name == section_names::compactUnwind) {
+  if (name == section_names::compactUnwind) {
       if (segname == segment_names::ld)
         return target->wordSize == 8 ? 32 : 20;
   }
+  if (config->icfLevel == ICFLevel::none)
+    return {};
+
+  if (name == section_names::cfString && segname == segment_names::data)
+    return target->wordSize == 8 ? 32 : 16;
+  if (name == section_names::objcClassRefs && 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 *);
 
 extern std::vector<ConcatInputSection *> inputSections;
 
 namespace section_names {
 
 constexpr const char authGot[] = "__auth_got";
 constexpr const char authPtr[] = "__auth_ptr";
 constexpr const char binding[] = "__binding";

 constexpr const char lazySymbolPtr[] = "__la_symbol_ptr";
 constexpr const char lazyBinding[] = "__lazy_binding";
 constexpr const char literals[] = "__literals";
 constexpr const char moduleInitFunc[] = "__mod_init_func";
 constexpr const char moduleTermFunc[] = "__mod_term_func";
 constexpr const char nonLazySymbolPtr[] = "__nl_symbol_ptr";
 constexpr const char objcCatList[] = "__objc_catlist";
 constexpr const char objcClassList[] = "__objc_classlist";
+constexpr const char objcClassRefs[] = "__objc_classrefs";
 constexpr const char objcConst[] = "__objc_const";
 constexpr const char objcImageInfo[] = "__objc_imageinfo";
 constexpr const char objcNonLazyCatList[] = "__objc_nlcatlist";
 constexpr const char objcNonLazyClassList[] = "__objc_nlclslist";
 constexpr const char objcProtoList[] = "__objc_protolist";
 constexpr const char pageZero[] = "__pagezero";
 constexpr const char pointers[] = "__pointers";
 constexpr const char rebase[] = "__rebase";

lld/MachO/InputSection.cpp

bool macho::isCodeSection(const InputSection *isec) {
   return false;
 }
 
 bool macho::isCfStringSection(const InputSection *isec) {
   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;
+}
+
 std::string lld::toString(const InputSection *isec) {
   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
 }

lld/test/MachO/objc-classrefs-dedup.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/defs.s -o %t/defs.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/refs1.s -o %t/refs1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/refs2.s -o %t/refs2.o
+# RUN: %lld -lSystem -dylib %t/defs.o -o %t/libdefs.dylib
+# RUN: %lld -lSystem -dylib --icf=all %t/refs1.o %t/refs2.o %t/libdefs.dylib -o %t/out
+# RUN: llvm-objdump --macho --section-headers --bind %t/out | FileCheck %s \
+# RUN:   --implicit-check-not __objc_classrefs
+
+## Check that we only have 3 (unique) entries
+# CHECK:      Sections:
+# CHECK-NEXT: Idx Name             Size
+# CHECK:          __objc_classrefs 00000018
+
+## And only two binds
+# CHECK:       Bind table:
+# CHECK-NEXT:  segment  section           address  type     addend dylib    symbol
+# CHECK-DAG:   __DATA   __objc_classrefs  {{.*}}   pointer       0 libdefs  _OBJC_CLASS_$_Bar
+# CHECK-DAG:   __DATA   __objc_classrefs  {{.*}}   pointer       0 libdefs  _OBJC_CLASS_$_Foo
+
+#--- defs.s
+.globl _OBJC_CLASS_$_Foo, _OBJC_CLASS_$_Bar
+.section __DATA,__objc_data
+_OBJC_CLASS_$_Foo:
+ .quad 123
+
+_OBJC_CLASS_$_Bar:
+ .quad 456
+
+.subsections_via_symbols
+
+#--- refs1.s
+.globl _OBJC_CLASS_$_Baz
+
+.section __DATA,__objc_data
+_OBJC_CLASS_$_Baz:
+ .quad 789
+
+.section __DATA,__objc_classrefs
+.quad _OBJC_CLASS_$_Foo
+.quad _OBJC_CLASS_$_Bar
+.quad _OBJC_CLASS_$_Baz
+.quad _OBJC_CLASS_$_Baz
+
+.subsections_via_symbols
+
+#--- refs2.s
+.section __DATA,__objc_classrefs
+.quad _OBJC_CLASS_$_Foo
+.quad _OBJC_CLASS_$_Bar
+
+.subsections_via_symbols