[lld-macho] Deduplicate CFStrings

[int3]

Summary

__cfstring is a special literal section, so instead of breaking it up
at symbol boundaries, we break it up at fixed-width boundaries (since
each literal is the same size). Symbols can only occur at one of those
boundaries, so this is strictly more powerful than
.subsections_via_symbols.

With that in place, we then run the section through ICF.

This change is about perf-neutral when linking chromium_framework.

[int3]

don't create extra InputSections unless ICF is enabled

[int3]

[gkm]

LGTM

lld/MachO/InputFiles.cpp

287

lld/test/MachO/cfstring-dedup.s

76

Length of UTF-8 "foo" is 3, but length of UTF-16 "foo" (or rather "foo\0") is 4? I do see that l_.str.2 has an extra 0 terminator. Is that detail relevant? If so, it could use a comment.

[int3]

lld/test/MachO/cfstring-dedup.s

76

yeah, the idea was to check that we would correctly handle utf-16 strings with null bytes in them. TBH, utf-8 *should* support encoding null bytes too, but 1) ld64 doesn't handle that correctly either and 2) clang will generate utf-16 CFStrings if their literal contains a null byte. Yeah, I'll add all that in a comment...

lld/MachO/ICF.cpp

void macho::foldIdenticalSections() {
   TimeTraceScope timeScope("Fold Identical Code Sections");
   // The ICF equivalence-class segregation algorithm relies on pre-computed
   // hashes of InputSection::data for the ConcatOutputSection::inputs and all
   // sections referenced by their relocs. We could recursively traverse the
   // relocs to find every referenced InputSection, but that precludes easy
   // parallelization. Therefore, we hash every InputSection here where we have
   // them all accessible as simple vectors.
   std::vector<ConcatInputSection *> codeSections;
+  std::vector<ConcatInputSection *> cfStringSections;
 
   // ICF can't fold functions with unwind info
   DenseSet<const InputSection *> functionsWithUnwindInfo =
       target->wordSize == 8 ? findFunctionsWithUnwindInfo<uint64_t>()
                             : findFunctionsWithUnwindInfo<uint32_t>();
 
   // 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()
   uint64_t icfUniqueID = inputSections.size();
   for (ConcatInputSection *isec : inputSections) {
-    bool isHashable = isCodeSection(isec) && !isec->shouldOmitFromOutput() &&
+    bool isHashable = (isCodeSection(isec) || isCfStringSection(isec)) &&
+                      !isec->shouldOmitFromOutput() &&
                       !functionsWithUnwindInfo.contains(isec) &&
                       isec->isHashableForICF();
     if (isHashable) {
+      if (isCodeSection(isec))
         codeSections.push_back(isec);
+      else {
+        assert(isCfStringSection(isec));
+        cfStringSections.push_back(isec);
+      }
     } else {
       isec->icfEqClass[0] = ++icfUniqueID;
     }
   }
-  parallelForEach(codeSections,
+  std::vector<ConcatInputSection *> hashable(codeSections);
+  hashable.insert(hashable.end(), cfStringSections.begin(),
+                  cfStringSections.end());
+  parallelForEach(hashable,
                   [](ConcatInputSection *isec) { isec->hashForICF(); });
   // Now that every input section is either hashed or marked as unique, run the
   // segregation algorithm to detect foldable subsections.
+  // We dedup cfStringSections first since code sections may refer to them, but
+  // not vice-versa.
+  ICF(cfStringSections).run();
   ICF(codeSections).run();
 }

lld/MachO/InputFiles.cpp

if (sectionType(sec.flags) == S_CSTRING_LITERALS ||
             make<CStringInputSection>(segname, name, this, data, align, flags);
         // FIXME: parallelize this?
         cast<CStringInputSection>(isec)->splitIntoPieces();
       } else {
         isec = make<WordLiteralInputSection>(segname, name, this, data, align,
                                              flags);
       }
       subsections.push_back({{0, isec}});
+    } else if (config->icfLevel != ICFLevel::none &&
+               (name == section_names::cfString &&
+                segname == segment_names::data)) {
+      uint64_t literalSize = target->wordSize == 8 ? 32 : 16;
+      subsections.push_back({});
+      SubsectionMap &subsecMap = subsections.back();
+      for (uint64_t off = 0; off < data.size(); off += literalSize)
+        subsecMap.push_back(
+            {off, make<ConcatInputSection>(segname, name, this,
+                                           data.slice(off, literalSize), align,
+                                           flags)});
     } else {
       auto *isec =
           make<ConcatInputSection>(segname, name, this, data, align, flags);
       if (!(isDebugSection(isec->flags) &&
             isec->segname == segment_names::dwarf)) {
         subsections.push_back({{0, isec}});
       } else {
         // Instead of emitting DWARF sections, we emit STABS symbols to the
if ((sym.n_type & N_TYPE) == N_SECT) {
       if (subsecMap.empty())
         continue;
       symbolsBySection[sym.n_sect - 1].push_back(i);
     } else {
       symbols[i] = parseNonSectionSymbol(sym, name);
     }
   }
 
-  // Calculate symbol sizes and create subsections by splitting the sections
-  // along symbol boundaries.
   for (size_t i = 0; i < subsections.size(); ++i) {
     SubsectionMap &subsecMap = subsections[i];
     if (subsecMap.empty())
       continue;
 
     std::vector<uint32_t> &symbolIndices = symbolsBySection[i];
-    llvm::stable_sort(symbolIndices, [&](uint32_t lhs, uint32_t rhs) {
-      return nList[lhs].n_value < nList[rhs].n_value;
-    });
     uint64_t sectionAddr = sectionHeaders[i].addr;
     uint32_t sectionAlign = 1u << sectionHeaders[i].align;
 
+    InputSection *isec = subsecMap.back().isec;
+    // __cfstring has already been split into subsections during
+    // parseSections(), so we simply need to match Symbols to the corresponding
+    // subsection here.
+    if (config->icfLevel != ICFLevel::none && isCfStringSection(isec)) {
+      for (size_t j = 0; j < symbolIndices.size(); ++j) {
+        uint32_t symIndex = symbolIndices[j];
+        const NList &sym = nList[symIndex];
+        StringRef name = strtab + sym.n_strx;
+        uint64_t symbolOffset = sym.n_value - sectionAddr;
+        InputSection *isec = findContainingSubsection(subsecMap, &symbolOffset);
+        if (symbolOffset != 0) {
+          error(toString(this) + ": __cfstring contains symbol " + name +
+                " at misaligned offset");
+          continue;
+        }
+        symbols[symIndex] = createDefined(sym, name, isec, 0, isec->getSize());
+      }
+      continue;
+    }
+
+    // Calculate symbol sizes and create subsections by splitting the sections
+    // along symbol boundaries.
     // We populate subsecMap by repeatedly splitting the last (highest address)
     // subsection.
+    llvm::stable_sort(symbolIndices, [&](uint32_t lhs, uint32_t rhs) {
+      return nList[lhs].n_value < nList[rhs].n_value;
+    });
     SubsectionEntry subsecEntry = subsecMap.back();
     for (size_t j = 0; j < symbolIndices.size(); ++j) {
       uint32_t symIndex = symbolIndices[j];
       const NList &sym = nList[symIndex];
       StringRef name = strtab + sym.n_strx;
       InputSection *isec = subsecEntry.isec;
 
       uint64_t subsecAddr = sectionAddr + subsecEntry.offset;

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 *);
+
 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 bitcodeBundle[] = "__bundle";

lld/MachO/InputSection.cpp

bool macho::isCodeSection(const InputSection *isec) {
   if (isec->segname == segment_names::text)
     return StringSwitch<bool>(isec->name)
         .Cases(section_names::textCoalNt, section_names::staticInit, true)
         .Default(false);
 
   return false;
 }
 
+bool macho::isCfStringSection(const InputSection *isec) {
+  return isec->name == section_names::cfString &&
+         isec->segname == segment_names::data;
+}
+
 std::string lld::toString(const InputSection *isec) {
   return (toString(isec->file) + ":(" + isec->name + ")").str();
 }

lld/test/MachO/Inputs/MacOSX.sdk/System/Library/Frameworks/CoreFoundation.framework/CoreFoundation.tbd

 --- !tapi-tbd-v3
 archs:            [ x86_64 ]
 uuids:            [ 'x86_64: 00000000-0000-0000-0000-000000000000' ]
 platform:         macosx
 install-name:     '/System/Library/Frameworks/CoreFoundation.framework/CoreFoundation'
 current-version:  0001.001.1
 compatibility-version: 150
 exports:
   - archs:         [ 'x86_64' ]
-    symbols:       [ '__CFBigNumGetInt128' ]
+    symbols:       [ __CFBigNumGetInt128, ___CFConstantStringClassReference ]
     objc-classes:  [ NSObject ]
     objc-ivars:    [ NSConstantArray._count ]
     objc-eh-types: [ NSException ]
 ...

lld/test/MachO/cfstring-dedup.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/foo1.s -o %t/foo1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/foo2.s -o %t/foo2.o
+# RUN: %lld -dylib --icf=all -framework CoreFoundation %t/foo1.o %t/foo2.o -o %t/foo
+# RUN: llvm-objdump --macho --rebase --bind --syms -d %t/foo | FileCheck %s
+
+# CHECK:       (__TEXT,__text) section
+# CHECK-NEXT:  _foo1:
+# CHECK-NEXT:  _foo2:
+# CHECK-NEXT:       movq    _named_cfstring(%rip), %rax
+# CHECK-NEXT:  _foo1_utf16:
+# CHECK-NEXT:       movq    [[#]](%rip), %rax
+# CHECK-NEXT:  _named_foo1:
+# CHECK-NEXT:  _named_foo2:
+# CHECK-NEXT:       movq    _named_cfstring(%rip), %rax
+# CHECK-NEXT:  _foo2_utf16:
+# CHECK-NEXT:       movq    [[#]](%rip), %rax
+
+# CHECK:       SYMBOL TABLE:
+# CHECK-DAG:   [[#%.16x,FOO:]] g     F __TEXT,__text _foo1
+# CHECK-DAG:   [[#FOO]]        g     F __TEXT,__text _foo2
+
+## Make sure we don't emit redundant bind / rebase opcodes for folded sections.
+# CHECK:       Rebase table:
+# CHECK-NEXT:  segment  section          address  type
+# CHECK-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer
+# CHECK-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer
+# CHECK-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer
+# CHECK-EMPTY:
+# CHECK-NEXT:  Bind table:
+# 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:
+  .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:
+  .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  4 ## strlen
+
+.text
+.globl  _foo1, _foo1_utf16, _named_foo1
+_foo1:
+  movq L__unnamed_cfstring_(%rip), %rax
+
+_foo1_utf16:
+  movq L__unnamed_cfstring_.2(%rip), %rax
+
+_named_foo1:
+  movq _named_cfstring(%rip), %rax
+
+.subsections_via_symbols
+
+#--- foo2.s
+.cstring
+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
+  .p2align  1
+l_.str.2:
+  .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  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/invalid/cfstring.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: not %lld -dylib -framework CoreFoundation --icf=all %t/test.o 2>&1 | FileCheck %s
+# CHECK: error: {{.*}}test.o: __cfstring contains symbol _uh_oh at misaligned offset
+
+.cstring
+L_.str:
+  .asciz  "foo"
+
+.section  __DATA,__cfstring
+.p2align  3
+L__unnamed_cfstring_:
+  .quad  ___CFConstantStringClassReference
+  .long  1992 ## utf-8
+_uh_oh:
+  .space  4
+  .quad  L_.str
+  .quad  3 ## strlen