[lld-macho] Fold cfstrings with --deduplicate-literals

[keith]

Summary

Similar to cstrings ld64 always deduplicates cfstrings. This was already
being done when enabling ICF, but for debug builds you may want to flip
this on if you cannot eliminate your instances of this, so this change
makes --deduplicate-literals also apply to cfstrings.

[keith]

Here's a repro case where this causes issues https://github.com/tapthaker/lld-reproducer, very similar to the standard cstring cases.

lld/MachO/ICF.cpp

398

I'm not happy with hijacking this function for this specific use case, so it would probably make sense for me to try to extract something here

[int3]

lgtm

lld/MachO/Driver.cpp

1669–1671

this is the more typical codebase convention

lld/MachO/ICF.cpp

398

yeah that would be nice but no rush

lld/test/MachO/cfstring-dedup.s

40–51

isn't this identical to the CHECK lines above? don't think we need to define a separate CHECK prefix

[keith]

style fixes, use single new prefix in test

lld/MachO/ICF.cpp

398

Ok thanks, we can see how this evolves a bit then I guess

lld/test/MachO/cfstring-dedup.s

40–51

So this part is, but the first CHECK block isn't valid for this codepath, since it expects TEXT,text folding as well. I've combined these to avoid the duplication and pointed the original test to both prefixes, wdyt?

[int3]

lld/test/MachO/cfstring-dedup.s

40–51

oh right. Yeah, this is a good solution, thanks!

lld/MachO/Driver.cpp

if (config->deadStrip)
       markLive();
 
     // ICF assumes that all literals have been folded already, so we must run
     // foldIdenticalLiterals before foldIdenticalSections.
     foldIdenticalLiterals();
     if (config->icfLevel != ICFLevel::none) {
       if (config->icfLevel == ICFLevel::safe)
         markAddrSigSymbols();
-      foldIdenticalSections();
+      foldIdenticalSections(/*onlyCfStrings=*/false);
+    } else if (config->dedupLiterals) {
+      foldIdenticalSections(/*onlyCfStrings=*/true);
     }
 
     // Write to an output file.
     if (target->wordSize == 8)
       writeResult<LP64>();
     else
       writeResult<ILP32>();
 

lld/MachO/ICF.h

 #include <vector>
 
 namespace lld {
 namespace macho {
 class Symbol;
 
 void markAddrSigSymbols();
 void markSymAsAddrSig(Symbol *s);
-void foldIdenticalSections();
+void foldIdenticalSections(bool onlyCfStrings);
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/ICF.cpp

for (const Reloc &r : isec->relocs) {
       if (auto *sym = r.referent.dyn_cast<Symbol *>())
         markSymAsAddrSig(sym);
       else
         error(toString(isec) + ": unexpected section relocation");
     }
   }
 }
 
-void macho::foldIdenticalSections() {
+void macho::foldIdenticalSections(bool onlyCfStrings) {
   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.
 
   // 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 *> hashable;
   uint64_t icfUniqueID = inputSections.size();
   for (ConcatInputSection *isec : inputSections) {
     // FIXME: consider non-code __text sections as hashable?
     bool isHashable =
+        (!onlyCfStrings || isCfStringSection(isec)) &&
         (isCodeSection(isec) || isCfStringSection(isec) ||
          isClassRefsSection(isec) || isGccExceptTabSection(isec)) &&
         !isec->keepUnique && !isec->shouldOmitFromOutput() &&
         sectionType(isec->getFlags()) == MachO::S_REGULAR;
     if (isHashable) {
       hashable.push_back(isec);
       for (Defined *d : isec->symbols)
         if (d->unwindEntry)

lld/MachO/InputFiles.cpp

 //
 // 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::compactUnwind) {
     if (segname == segment_names::ld)
       return target->wordSize == 8 ? 32 : 20;
   }
-  if (config->icfLevel == ICFLevel::none)
+  if (!config->dedupLiterals)
     return {};
 
   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;
   return {};
 }
 
 static Error parseCallGraph(ArrayRef<uint8_t> data,
                             std::vector<CallGraphEntry> &callGraph) {
   TimeTraceScope timeScope("Parsing call graph section");

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
+# RUN: llvm-objdump --macho --rebase --bind --syms -d %t/foo | FileCheck %s --check-prefixes=CHECK,LITERALS
+# RUN: %lld -dylib --deduplicate-literals -framework CoreFoundation %t/foo1.o %t/foo2.o -o %t/foo
+# RUN: llvm-objdump --macho --rebase --bind --syms -d %t/foo | FileCheck %s --check-prefix=LITERALS
 
 # 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:
+# LITERALS:       Rebase table:
+# LITERALS-NEXT:  segment  section          address  type
+# LITERALS-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer
+# LITERALS-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer
+# LITERALS-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer
+# LITERALS-EMPTY:
+# LITERALS-NEXT:  Bind table:
+# LITERALS-NEXT:  segment      section      address  type       addend dylib            symbol
+# LITERALS-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer         0 CoreFoundation   ___CFConstantStringClassReference
+# LITERALS-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer         0 CoreFoundation   ___CFConstantStringClassReference
+# LITERALS-NEXT:  __DATA_CONST __cfstring   {{.*}}   pointer         0 CoreFoundation   ___CFConstantStringClassReference
+# LITERALS-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