[lld-macho] Extend ICF to literal sections

[int3]

Summary

Literal sections can be deduplicated before running ICF. That makes it
easy to compare them during ICF: we can tell if two literals are
constant-equal by comparing their offsets in their OutputSection.

LLD-ELF takes a similar approach.

[int3]

lld/MachO/ICF.cpp

107–108

we don't want to compare value early because two symbols with different values may point to the same literal

[int3]

rebase + fix absolute symbol check

[gkm]

Groovy!

lld/MachO/ICF.cpp

112–119

I prefer this for convenient breakpoint locations when particular conditions fail.

117–119

Ditto.

122

Ditto; and I think you meant this, no?

return da->value == db->value;

141

209

210

Super nitty: I prefer to see the simpler oparand(s) come earlier in the expression.

lld/test/MachO/icf-literals.s

33–36

[int3]

fix hash

[int3]

lld/test/MachO/icf-literals.s

33–36

oops. I guess I should add a section of callqs like the icf.s test to check that we aren't deduplicating things unexpectedly

[int3]

lld/MachO/ICF.cpp

112–119

it feels unfortunate to contort the code for easier breakpointing. Is the goal to be able to breakpoint right before function exit? for that case, could we just set a breakpoint at the retq instruction's address? (I checked the disassembly, and clang does indeed emit a single retq for this whole function)

[gkm]

lld/MachO/ICF.cpp

112–119

IMO, it's not contortion so much as vertical expansion! ;)
I want to see if a particular predicate fails, so I'll breakpoint the return false; beneath it.

[int3]

lld/MachO/ICF.cpp

112–119

hm, so the idea is that you're more likely to want to debug when things don't compare to be equal?

[int3]

lld/MachO/ICF.cpp

112–119

IMO, it's not contortion so much as vertical expansion! ;)

I think it makes for more confusing code, because it obscures when fall-through behavior (to the return true;) is actually needed.

[gkm]

lld/MachO/ICF.cpp

112–119

hm, so the idea is that you're more likely to want to debug when things don't compare to be equal?

So far, all of my debugging has been to see when predicates unexpectedly fail. We don't need to debate this any further. Do what you think best. ;)

112–119

It makes sense when you recognize that everything follows a regular pattern: A sequence of if (UNEQUAL) return false; falling through to return true;

[gkm]

lld/MachO/ICF.cpp

112–119

Overall, the if (UNEQUAL) return false; pattern serves all breakpointing purposes: when there is an unexpected predicate failure, I break on the return false;, and when there is an unexpected predicate success, I break on the statement following the entire if statement. I like it. It works for me. FYI, the earliest versions of equalsConstant() and equalsVariable() were beautiful single statements: return MASSIVE-MULTILINE-COMPOUND-PREDICATE, but then I needed to debug and wanted fine-grained control over breakpoints. ;)

[int3]

Mm I see. I think it's easy enough to switch between the two forms for debugging purposes, so I'm landing it as-is...

[thakis]

lld/MachO/Writer.cpp

948

I rebased the cstring alignment patch across this naively (a8a6e5b094aac642f436390294ec837400c521bb) and this came out pretty weird (because for non-deduped cstring sections this doesn't do any folding).

Maybe CStringSection should keep overriding finalize() and also add an empty virtual foldLiterals that DedupCStringSection overrides?

[int3]

lld/MachO/Writer.cpp

948

I think it would be confusing / a potential source of bugs to have CStringSection and DedupCStringSection finalized at different points in the link. Perhaps a comment here would be sufficient?

[int3]

lld/MachO/Writer.cpp

948

comment added in D105044

lld/MachO/Driver.cpp

bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
   config->deadStripDylibs = args.hasArg(OPT_dead_strip_dylibs);
   config->demangle = args.hasArg(OPT_demangle);
   config->implicitDylibs = !args.hasArg(OPT_no_implicit_dylibs);
   config->emitFunctionStarts =
       args.hasFlag(OPT_function_starts, OPT_no_function_starts, true);
   config->emitBitcodeBundle = args.hasArg(OPT_bitcode_bundle);
   config->emitDataInCodeInfo =
       args.hasFlag(OPT_data_in_code_info, OPT_no_data_in_code_info, true);
-  config->dedupLiterals = args.hasArg(OPT_deduplicate_literals);
+  config->icfLevel = getICFLevel(args);
+  config->dedupLiterals = args.hasArg(OPT_deduplicate_literals) ||
+                          config->icfLevel != ICFLevel::none;
 
   // FIXME: Add a commandline flag for this too.
   config->zeroModTime = getenv("ZERO_AR_DATE");
 
   std::array<PlatformKind, 3> encryptablePlatforms{
       PlatformKind::iOS, PlatformKind::watchOS, PlatformKind::tvOS};
   config->emitEncryptionInfo =
       args.hasFlag(OPT_encryptable, OPT_no_encryption,
#endif
   if (const Arg *arg =
           args.getLastArg(OPT_flat_namespace, OPT_twolevel_namespace))
     config->namespaceKind = arg->getOption().getID() == OPT_twolevel_namespace
                                 ? NamespaceKind::twolevel
                                 : NamespaceKind::flat;
 
   config->undefinedSymbolTreatment = getUndefinedSymbolTreatment(args);
 
-  config->icfLevel = getICFLevel(args);
-
   if (config->outputType == MH_EXECUTE)
     config->entry = symtab->addUndefined(args.getLastArgValue(OPT_e, "_main"),
                                          /*file=*/nullptr,
                                          /*isWeakRef=*/false);
 
   config->librarySearchPaths =
       getLibrarySearchPaths(args, config->systemLibraryRoots);
   config->frameworkSearchPaths =

lld/MachO/ICF.cpp

auto f = [&](const Reloc &ra, const Reloc &rb) {
     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)) {
         const auto *da = dyn_cast<Defined>(sa);
         const auto *db = dyn_cast<Defined>(sb);
-        if (da->value != db->value)
-          return false;
-        if (da->isAbsolute() != db->isAbsolute())
-          return false;
-        if (da->isec) {
+        if (da->isec && db->isec) {
           if (da->isec->kind() != db->isec->kind())
             return false;
           if (const auto *isecA = dyn_cast<ConcatInputSection>(da->isec)) {
             const auto *isecB = cast<ConcatInputSection>(db->isec);
-            if (isecA->icfEqClass[icfPass % 2] !=
-                isecB->icfEqClass[icfPass % 2])
-              return false;
-          } else {
-            // FIXME: implement ICF for other InputSection kinds
-            return false;
+            return da->value == db->value && isecA->icfEqClass[icfPass % 2] ==
+                                                 isecB->icfEqClass[icfPass % 2];
           }
+          // Else we have two literal sections. References to them are
+          // constant-equal if their offsets in the output section are equal.
+          return da->isec->parent == db->isec->parent &&
+                 da->isec->getOffset(da->value) ==
+                     db->isec->getOffset(db->value);
         }
+        assert(da->isAbsolute() && db->isAbsolute());
+        return da->value == db->value;
       } else if (isa<DylibSymbol>(sa)) {
         // There is one DylibSymbol per gotIndex and we already checked for
         // symbol equality, thus we know that these must be different.
         return false;
       } else {
         llvm_unreachable("equalsVariable symbol kind");
       }
     } else {
       const auto *sa = ra.referent.get<InputSection *>();
       const auto *sb = rb.referent.get<InputSection *>();
       if (sa->kind() != sb->kind())
         return false;
       if (const auto *isecA = dyn_cast<ConcatInputSection>(sa)) {
         const auto *isecB = cast<ConcatInputSection>(sb);
-        if (isecA->icfEqClass[icfPass % 2] != isecB->icfEqClass[icfPass % 2])
-          return false;
+        return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2];
       } else {
-        // FIXME: implement ICF for other InputSection kinds
-        return false;
+        assert(isa<CStringInputSection>(sa) ||
+               isa<WordLiteralInputSection>(sa));
+        return sa->getOffset(ra.addend) == sb->getOffset(rb.addend);
       }
     }
-    return true;
   };
   return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
                     f);
 }
 
 // Find the first InputSection after BEGIN whose equivalence class differs
 size_t ICF::findBoundary(size_t begin, size_t end) {
   uint64_t beginHash = icfInputs[begin]->icfEqClass[icfPass % 2];
void ICF::run() {
   for (icfPass = 0; icfPass < 2; ++icfPass) {
     parallelForEach(icfInputs, [&](ConcatInputSection *isec) {
       uint64_t hash = isec->icfEqClass[icfPass % 2];
       for (const Reloc &r : isec->relocs) {
         if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
           if (auto *dylibSym = dyn_cast<DylibSymbol>(sym))
             hash += dylibSym->stubsHelperIndex;
           else if (auto *defined = dyn_cast<Defined>(sym)) {
+            if (defined->isec) {
+              if (auto isec = dyn_cast<ConcatInputSection>(defined->isec))
+                hash += defined->value + isec->icfEqClass[icfPass % 2];
+              else
+                hash += defined->isec->kind() +
+                        defined->isec->getOffset(defined->value);
+            } else {
               hash += defined->value;
-            if (defined->isec)
-              if (auto *isec = cast<ConcatInputSection>(defined->isec))
-                hash += isec->icfEqClass[icfPass % 2];
-            // FIXME: implement ICF for other InputSection kinds
+            }
           } else
             llvm_unreachable("foldIdenticalSections symbol kind");
         }
       }
       // Set MSB to 1 to avoid collisions with non-hashed classes.
       isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 63);
     });
   }

lld/MachO/InputSection.cpp

case S_REGULAR:
     // One might hope that we could hash __TEXT,__const subsections to fold
     // references to duplicated values, but alas, many tests fail.
     return false;
   case S_CSTRING_LITERALS:
   case S_4BYTE_LITERALS:
   case S_8BYTE_LITERALS:
   case S_16BYTE_LITERALS:
   case S_LITERAL_POINTERS:
-    // FIXME(jezng): We should not have any ConcatInputSections of these types
-    // when running ICF.
-    return false;
+    llvm_unreachable("found unexpected literal type in ConcatInputSection");
   case S_ZEROFILL:
   case S_GB_ZEROFILL:
   case S_NON_LAZY_SYMBOL_POINTERS:
   case S_LAZY_SYMBOL_POINTERS:
   case S_SYMBOL_STUBS:
   case S_MOD_INIT_FUNC_POINTERS:
   case S_MOD_TERM_FUNC_POINTERS:
   case S_COALESCED:

lld/MachO/Options.td

def time_trace: Flag<["--"], "time-trace">, HelpText<"Record time trace">,
     Group<grp_lld>;
 def time_trace_granularity_eq: Joined<["--"], "time-trace-granularity=">,
     HelpText<"Minimum time granularity (in microseconds) traced by time profiler">,
     Group<grp_lld>;
 def time_trace_file_eq: Joined<["--"], "time-trace-file=">,
     HelpText<"Specify time trace output file">,
     Group<grp_lld>;
 def deduplicate_literals: Flag<["--"], "deduplicate-literals">,
-    HelpText<"Enable literal deduplication">,
+    HelpText<"Enable literal deduplication. This is implied by --icf={safe,all}">,
     Group<grp_lld>;
 def print_dylib_search: Flag<["--"], "print-dylib-search">,
     HelpText<"Print which paths lld searched when trying to find dylibs">,
     Group<grp_lld>;
 def icf_eq: Joined<["--"], "icf=">,
     HelpText<"Set level for identical code folding (default: none)">,
     MetaVarName<"[none,safe,all]">,
     Group<grp_lld>;

lld/MachO/SyntheticSections.h

private:
   uint64_t xarSize;
 };
 
 class CStringSection final : public SyntheticSection {
 public:
   CStringSection();
   void addInput(CStringInputSection *);
   uint64_t getSize() const override { return builder.getSize(); }
-  void finalize() override;
+  void finalizeContents();
   bool isNeeded() const override { return !inputs.empty(); }
   void writeTo(uint8_t *buf) const override { builder.write(buf); }
 
   std::vector<CStringInputSection *> inputs;
 
 private:
   llvm::StringTableBuilder builder;
 };

lld/MachO/SyntheticSections.cpp

CStringSection::CStringSection()
   flags = S_CSTRING_LITERALS;
 }
 
 void CStringSection::addInput(CStringInputSection *isec) {
   isec->parent = this;
   inputs.push_back(isec);
 }
 
-void CStringSection::finalize() {
+void CStringSection::finalizeContents() {
   // Add all string pieces to the string table builder to create section
   // contents.
   for (const CStringInputSection *isec : inputs)
     for (size_t i = 0, e = isec->pieces.size(); i != e; ++i)
       if (isec->pieces[i].live)
         builder.add(isec->getCachedHashStringRef(i));
 
   // Fix the string table content. After this, the contents will never change.

lld/MachO/Writer.cpp

 class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
   void scanRelocations();
   void scanSymbols();
   template <class LP> void createOutputSections();
   template <class LP> void createLoadCommands();
+  void foldIdenticalLiterals();
   void foldIdenticalSections();
   void finalizeAddresses();
   void finalizeLinkEditSegment();
   void assignAddresses(OutputSegment *);
 
   void openFile();
   void writeSections();
   void writeUuid();
if (ssec->isNeeded()) {
       }
     }
   }
 
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   linkEditSegment = getOrCreateOutputSegment(segment_names::linkEdit);
 }
 
+void Writer::foldIdenticalLiterals() {
+  if (in.cStringSection)
+    in.cStringSection->finalizeContents();
+  // TODO: WordLiteralSection & CFStringSection should be finalized here too
+}
+
 void Writer::foldIdenticalSections() {
   if (config->icfLevel == ICFLevel::none)
     return;
   ConcatOutputSection *textOutputSection = concatOutputSections.lookup(
       maybeRenameSection({segment_names::text, section_names::text}));
   if (textOutputSection == nullptr)
     return;
 
void Writer::foldIdenticalSections() {
   uint64_t icfUniqueID = inputSections.size();
   for (InputSection *isec : inputSections) {
     if (auto *concatIsec = dyn_cast<ConcatInputSection>(isec)) {
       if (concatIsec->isHashableForICF(isec->parent == textOutputSection))
         hashable.push_back(concatIsec);
       else
         concatIsec->icfEqClass[0] = ++icfUniqueID;
     }
-    // FIXME: hash literal sections here?
   }
+  // FIXME: hash literal sections here too?
   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
   ICF(textOutputSection->inputs).run();
   size_t oldSize = textOutputSection->inputs.size();
   textOutputSection->eraseOmittedInputSections();
   size_t newSize = textOutputSection->inputs.size();

 template <class LP> void Writer::run() {
   if (config->entry && !isa<Undefined>(config->entry))
     prepareBranchTarget(config->entry);
   scanRelocations();
   if (in.stubHelper->isNeeded())
     in.stubHelper->setup();
   scanSymbols();
   createOutputSections<LP>();
+  // ICF assumes that all literals have been folded already, so we must run
+  // foldIdenticalLiterals before foldIdenticalSections.
+  foldIdenticalLiterals();
   foldIdenticalSections();
   // After this point, we create no new segments; HOWEVER, we might
   // yet create branch-range extension thunks for architectures whose
   // hardware call instructions have limited range, e.g., ARM(64).
   // The thunks are created as InputSections interspersed among
   // the ordinary __TEXT,_text InputSections.
   sortSegmentsAndSections();
   createLoadCommands<LP>();

lld/test/MachO/icf-literals.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: %lld -lSystem --icf=all -o %t/test %t/test.o
+# RUN: llvm-objdump --macho --syms -d %t/test | FileCheck %s
+
+# CHECK:      _main:
+# CHECK-NEXT: callq   _foo2_ref
+# CHECK-NEXT: callq   _foo2_ref
+# CHECK-NEXT: callq   _bar2_ref
+# CHECK-NEXT: callq   _bar2_ref
+# CHECK-NEXT: callq   _baz2_ref
+# CHECK-NEXT: callq   _baz2_ref
+# CHECK-NEXT: callq   _qux2_ref
+# CHECK-NEXT: callq   _qux2_ref
+
+# CHECK:      [[#%.16x,FOO:]]     l     O __TEXT,__cstring _foo1
+# CHECK-NEXT: [[#%.16x,FOO:]]     l     O __TEXT,__cstring _foo2
+# CHECK-NEXT: [[#%.16x,BAR:]]     l     O __TEXT,__cstring _bar1
+# CHECK-NEXT: [[#%.16x,BAR:]]     l     O __TEXT,__cstring _bar2
+# CHECK-NEXT: [[#%.16x,BAZ:]]     l     O __TEXT,__literals _baz1
+# CHECK-NEXT: [[#%.16x,BAZ:]]     l     O __TEXT,__literals _baz2
+# CHECK-NEXT: [[#%.16x,QUX:]]     l     O __TEXT,__literals _qux1
+# CHECK-NEXT: [[#%.16x,QUX:]]     l     O __TEXT,__literals _qux2
+# CHECK-NEXT: [[#%.16x,FOO_REF:]] l     F __TEXT,__text _foo1_ref
+# CHECK-NEXT: [[#%.16x,FOO_REF:]] l     F __TEXT,__text _foo2_ref
+# CHECK-NEXT: [[#%.16x,BAR_REF:]] l     F __TEXT,__text _bar1_ref
+# CHECK-NEXT: [[#%.16x,BAR_REF:]] l     F __TEXT,__text _bar2_ref
+# CHECK-NEXT: [[#%.16x,BAZ_REF:]] l     F __TEXT,__text _baz1_ref
+# CHECK-NEXT: [[#%.16x,BAZ_REF:]] l     F __TEXT,__text _baz2_ref
+# CHECK-NEXT: [[#%.16x,QUX_REF:]] l     F __TEXT,__text _qux1_ref
+# CHECK-NEXT: [[#%.16x,QUX_REF:]] l     F __TEXT,__text _qux2_ref
+
+## _foo1 vs _bar1: same section, different offsets
+## _foo1 vs _baz1: same offset, different sections
+
+.cstring
+_foo1:
+  .asciz "foo"
+_foo2:
+  .asciz "foo"
+_bar1:
+  .asciz "bar"
+_bar2:
+  .asciz "bar"
+
+.literal8
+_baz1:
+  .quad 0xdead
+_baz2:
+  .quad 0xdead
+_qux1:
+  .quad 0xbeef
+_qux2:
+  .quad 0xbeef
+
+.text
+_foo1_ref:
+  mov _foo1@GOTPCREL(%rip), %rax
+_foo2_ref:
+  mov _foo2@GOTPCREL(%rip), %rax
+_bar1_ref:
+  mov _bar1@GOTPCREL(%rip), %rax
+_bar2_ref:
+  mov _bar2@GOTPCREL(%rip), %rax
+_baz1_ref:
+  mov _baz1@GOTPCREL(%rip), %rax
+_baz2_ref:
+  mov _baz2@GOTPCREL(%rip), %rax
+_qux1_ref:
+  mov _qux1@GOTPCREL(%rip), %rax
+_qux2_ref:
+  mov _qux2@GOTPCREL(%rip), %rax
+
+.globl _main
+_main:
+  callq _foo1_ref
+  callq _foo2_ref
+  callq _bar1_ref
+  callq _bar2_ref
+  callq _baz1_ref
+  callq _baz2_ref
+  callq _qux1_ref
+  callq _qux2_ref
+
+.subsections_via_symbols