[lld-macho] Teach ICF to dedup functions with identical unwind info

[int3]

Summary

Dedup'ing unwind info is tricky because each CUE contains a different
function address, if ICF operated naively and compared the entire
contents of each CUE, entries with identical unwind info but belonging
to different functions would never be considered identical. To work
around this problem, we slice away the function address before
performing ICF. We rely on relocateCompactUnwind() to correctly handle
these truncated input sections.

Here are the numbers before and after D109944, D109945, and this diff
were applied, as tested on my 3.2 GHz 16-Core Intel Xeon W:

Without any optimizations:

           base           diff           difference (95% CI)
sys_time   0.849 ± 0.015  0.896 ± 0.012  [  +4.8% ..   +6.2%]
user_time  3.357 ± 0.030  3.512 ± 0.023  [  +4.3% ..   +5.0%]
wall_time  3.944 ± 0.039  4.032 ± 0.031  [  +1.8% ..   +2.6%]
samples    40             38

With -dead_strip:

           base           diff           difference (95% CI)
sys_time   0.847 ± 0.010  0.896 ± 0.012  [  +5.2% ..   +6.5%]
user_time  3.377 ± 0.014  3.532 ± 0.015  [  +4.4% ..   +4.8%]
wall_time  3.962 ± 0.024  4.060 ± 0.030  [  +2.1% ..   +2.8%]
samples    47             30

With -dead_strip and --icf=all:

           base           diff           difference (95% CI)
sys_time   0.935 ± 0.013  0.957 ± 0.018  [  +1.5% ..   +3.2%]
user_time  3.472 ± 0.022  6.531 ± 0.046  [ +87.6% ..  +88.7%]
wall_time  4.080 ± 0.040  5.329 ± 0.060  [ +30.0% ..  +31.2%]
samples    37             30

Unsurprisingly, ICF is now a lot slower, likely due to the much larger
number of input sections it needs to process. But the rest of the
linker only suffers a mild slowdown.

Note that the compact-unwind-bad-reloc.s test was expanded because we
now handle the relocation for CUE's function address in a separate code
path from the rest of the CUE relocations. The extended test covers both
code paths.

[int3]

This is an alternative to D106213: [lld-macho] Enable copy-on-write for input buffers and D106214: [lld-macho] ICF: Fold some sections with differing addends

[int3]

add comment

[oontvoo]

Unsurprisingly, ICF is now a lot slower, likely due to the much larger number of input sections it needs to process.

Is it worth making this an option that could be turned off?

[int3]

If there's demand for it I guess we can add it later. Maybe as part of some -O1/2/3 flags.

[int3]

rebase

[thakis]

I patched this in to play with it, and I discovered that this makes lld crash for the repro in comment 0 of https://bugs.llvm.org/show_bug.cgi?id=50411.

[int3]

That crash gets fixed by D112687. I think it'd be fairly awkward/tricky to write a test for that particular crash though

[int3]

update

[int3]

bumpibump @thakis

[int3]

Sigh I just spent a decent amount of time setting up a Linux env to track down my test failures in D113721, only to find that the culprit was really that I had it stacked upon this diff in my local copy :/

Can I get a stamp to land this?

[oontvoo]

LG

[int3]

Thanks!

lld/MachO/ICF.cpp

if (ra.referent.is<Symbol *>()) {
       const auto *sb = rb.referent.get<InputSection *>();
       isecA = dyn_cast<ConcatInputSection>(sa);
       if (!isecA)
         return true;
       isecB = cast<ConcatInputSection>(sb);
     }
     return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2];
   };
-  return std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(),
-                    f);
+  if (!std::equal(ia->relocs.begin(), ia->relocs.end(), ib->relocs.begin(), f))
+    return false;
+
+  // If there are symbols with associated unwind info, check that the unwind
+  // info matches. For simplicity, we only handle the case where there are only
+  // symbols at offset zero within the section (which is typically the case with
+  // .subsections_via_symbols.)
+  auto hasCU = [](Defined *d) { return d->compactUnwind; };
+  auto itA = std::find_if(ia->symbols.begin(), ia->symbols.end(), hasCU);
+  auto itB = std::find_if(ib->symbols.begin(), ib->symbols.end(), hasCU);
+  if (itA == ia->symbols.end())
+    return itB == ib->symbols.end();
+  if (itB == ib->symbols.end())
+    return false;
+  const Defined *da = *itA;
+  const Defined *db = *itB;
+  if (da->compactUnwind->icfEqClass[icfPass % 2] !=
+          db->compactUnwind->icfEqClass[icfPass % 2] ||
+      da->value != 0 || db->value != 0)
+    return false;
+  auto isZero = [](Defined *d) { return d->value == 0; };
+  return std::find_if_not(std::next(itA), ia->symbols.end(), isZero) ==
+             ia->symbols.end() &&
+         std::find_if_not(std::next(itB), ib->symbols.end(), isZero) ==
+             ib->symbols.end();
 }
 
 // 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];
   for (size_t i = begin + 1; i < end; ++i)
     if (beginHash != icfInputs[i]->icfEqClass[icfPass % 2])
       return i;
void macho::foldIdenticalSections() {
   // 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)) &&
                       !isec->shouldOmitFromOutput() && isec->isHashableForICF();
-    // ICF can't fold functions with unwind info
-    if (isHashable)
-      for (Defined *d : isec->symbols)
-        if (d->compactUnwind) {
-          isHashable = false;
-          break;
-        }
-
-    if (isHashable)
+    if (isHashable) {
       hashable.push_back(isec);
-    else
+      for (Defined *d : isec->symbols)
+        if (d->compactUnwind)
+          hashable.push_back(d->compactUnwind);
+    } else {
       isec->icfEqClass[0] = ++icfUniqueID;
     }
+  }
   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(hashable).run();
 }

lld/MachO/InputFiles.cpp

for (SubsectionMap &map : subsections) {
     cuSubsecMap = ↦
     break;
   }
   if (!cuSubsecMap)
     return;
 
   for (SubsectionEntry &entry : *cuSubsecMap) {
     ConcatInputSection *isec = cast<ConcatInputSection>(entry.isec);
+    // Hack!! Since each CUE contains a different function address, if ICF
+    // operated naively and compared the entire contents of each CUE, entries
+    // with identical unwind info but belonging to different functions would
+    // never be considered equivalent. To work around this problem, we slice
+    // away the function address here. (Note that we do not adjust the offsets
+    // of the corresponding relocations.) We rely on `relocateCompactUnwind()`
+    // to correctly handle these truncated input sections.
+    isec->data = isec->data.slice(target->wordSize);
+
     ConcatInputSection *referentIsec;
-    for (const Reloc &r : isec->relocs) {
-      if (r.offset != 0)
+    for (auto it = isec->relocs.begin(); it != isec->relocs.end();) {
+      Reloc &r = *it;
+      // We only wish to handle the relocation for CUE::functionAddress.
+      if (r.offset != 0) {
+        ++it;
         continue;
+      }
       uint64_t add = r.addend;
       if (auto *sym = cast_or_null<Defined>(r.referent.dyn_cast<Symbol *>())) {
         add += sym->value;
         referentIsec = cast<ConcatInputSection>(sym->isec);
       } else {
         referentIsec =
             cast<ConcatInputSection>(r.referent.dyn_cast<InputSection *>());
       }
       if (referentIsec->getSegName() != segment_names::text)
         error("compact unwind references address in " + toString(referentIsec) +
               " which is not in segment __TEXT");
       // The functionAddress relocations are typically section relocations.
       // However, unwind info operates on a per-symbol basis, so we search for
       // the function symbol here.
-      auto it = llvm::lower_bound(
+      auto symIt = llvm::lower_bound(
           referentIsec->symbols, add,
           [](Defined *d, uint64_t add) { return d->value < add; });
       // The relocation should point at the exact address of a symbol (with no
       // addend).
-      if (it == referentIsec->symbols.end() || (*it)->value != add) {
+      if (symIt == referentIsec->symbols.end() || (*symIt)->value != add) {
         assert(referentIsec->wasCoalesced);
+        ++it;
         continue;
       }
-      (*it)->compactUnwind = isec;
+      (*symIt)->compactUnwind = isec;
+      // Since we've sliced away the functionAddress, we should remove the
+      // corresponding relocation too. Given that clang emits relocations in
+      // reverse order of address, this relocation should be at the end of the
+      // vector for most of our input object files, so this is typically an O(1)
+      // operation.
+      it = isec->relocs.erase(it);
     }
   }
 }
 
 // The path can point to either a dylib or a .tbd file.
 static DylibFile *loadDylib(StringRef path, DylibFile *umbrella) {
   Optional<MemoryBufferRef> mbref = readFile(path);
   if (!mbref) {

lld/MachO/UnwindInfoSection.cpp

uint8_t *buf = reinterpret_cast<uint8_t *>(cuVector.data()) +
                    i * sizeof(CompactUnwindEntry<Ptr>);
     const Defined *d = symbolsVec[i].second;
     // Write the functionAddress.
     writeAddress(buf, d->getVA(), sizeof(Ptr) == 8 ? 3 : 2);
     if (!d->compactUnwind)
       return;
 
     // Write the rest of the CUE.
-    memcpy(buf, d->compactUnwind->data.data(), d->compactUnwind->data.size());
+    memcpy(buf + sizeof(Ptr), d->compactUnwind->data.data(),
+           d->compactUnwind->data.size());
     for (const Reloc &r : d->compactUnwind->relocs) {
       uint64_t referentVA = 0;
       if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
         if (!isa<Undefined>(referentSym)) {
           if (auto *defined = dyn_cast<Defined>(referentSym))
             checkTextSegment(defined->isec);
           // At this point in the link, we may not yet know the final address of
           // the GOT, so we just encode the index. We make it a 1-based index so
           // that we can distinguish the null pointer case.
           referentVA = referentSym->gotIndex + 1;
         }
       } else {
         auto *referentIsec = r.referent.get<InputSection *>();
-        ConcatInputSection *concatIsec = checkTextSegment(referentIsec);
-        if (!concatIsec->shouldOmitFromOutput())
-          referentVA = referentIsec->getVA(r.addend);
+        checkTextSegment(referentIsec);
       }
       writeAddress(buf + r.offset, referentVA, r.length);
     }
   });
 }
 
 // There should only be a handful of unique personality pointers, so we can
 // encode them as 2-bit indices into a small array.

lld/test/MachO/icf.s

 # CHECK: [[#%x,WITH_ALT_ENTRY:]]            l     F __TEXT,__text _no_alt_entry
 # CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_2:]] l     F __TEXT,__text _defined_ref_with_addend_1
 # CHECK: [[#%x,DEFINED_REF_WITH_ADDEND_2:]] l     F __TEXT,__text _defined_ref_with_addend_2
 # CHECK: [[#%x,RECURSIVE:]]                 l     F __TEXT,__text _recursive
 # CHECK: [[#%x,CALL_RECURSIVE_2:]]          l     F __TEXT,__text _call_recursive_1
 # CHECK: [[#%x,CALL_RECURSIVE_2:]]          l     F __TEXT,__text _call_recursive_2
 # CHECK: [[#%x,CHECK_LENGTH_1:]]            l     F __TEXT,__text _check_length_1
 # CHECK: [[#%x,CHECK_LENGTH_2:]]            l     F __TEXT,__text _check_length_2
-# CHECK: [[#%x,HAS_UNWIND_1:]]              l     F __TEXT,__text _has_unwind_1
+# CHECK: [[#%x,HAS_UNWIND_2:]]              l     F __TEXT,__text _has_unwind_1
 # CHECK: [[#%x,HAS_UNWIND_2:]]              l     F __TEXT,__text _has_unwind_2
+# CHECK: [[#%x,HAS_UNWIND_3:]]              l     F __TEXT,__text _has_unwind_3
 # CHECK: [[#%x,MUTALLY_RECURSIVE_2:]]       l     F __TEXT,__text _mutually_recursive_1
 # CHECK: [[#%x,MUTALLY_RECURSIVE_2:]]       l     F __TEXT,__text _mutually_recursive_2
 # CHECK: [[#%x,INIT_2:]]                    l     F __TEXT,__text _init_1
 # CHECK: [[#%x,INIT_2:]]                    l     F __TEXT,__text _init_2
 # CHECK: [[#%x,INIT_3:]]                    l     O __TEXT,__foo  _init_3
 ### FIXME: Mutually-recursive functions with identical bodies (see below)
 # COM:   [[#%x,ASYMMETRIC_RECURSIVE_2:]]    l   F __TEXT,__text _asymmetric_recursive_1
 # COM:   [[#%x,ASYMMETRIC_RECURSIVE_2]]     l   F __TEXT,__text _asymmetric_recursive_2

 # CHECK: callq 0x[[#%x,WITH_ALT_ENTRY:]]            <_with_alt_entry>
 # CHECK: callq 0x[[#%x,DEFINED_REF_WITH_ADDEND_2:]] <_defined_ref_with_addend_2>
 # CHECK: callq 0x[[#%x,DEFINED_REF_WITH_ADDEND_2:]] <_defined_ref_with_addend_2>
 # CHECK: callq 0x[[#%x,RECURSIVE:]]                 <_recursive>
 # CHECK: callq 0x[[#%x,CALL_RECURSIVE_2:]]          <_call_recursive_2>
 # CHECK: callq 0x[[#%x,CALL_RECURSIVE_2:]]          <_call_recursive_2>
 # CHECK: callq 0x[[#%x,CHECK_LENGTH_1:]]            <_check_length_1>
 # CHECK: callq 0x[[#%x,CHECK_LENGTH_2:]]            <_check_length_2>
-# CHECK: callq 0x[[#%x,HAS_UNWIND_1:]]              <_has_unwind_1>
 # CHECK: callq 0x[[#%x,HAS_UNWIND_2:]]              <_has_unwind_2>
+# CHECK: callq 0x[[#%x,HAS_UNWIND_2:]]              <_has_unwind_2>
+# CHECK: callq 0x[[#%x,HAS_UNWIND_3:]]              <_has_unwind_3>
 # CHECK: callq 0x[[#%x,MUTALLY_RECURSIVE_2:]]       <_mutually_recursive_2>
 # CHECK: callq 0x[[#%x,MUTALLY_RECURSIVE_2:]]       <_mutually_recursive_2>
 ## FIXME: Mutually-recursive functions with identical bodies (see below)
 # COM:   callq 0x[[#%x,ASYMMETRIC_RECURSIVE_2]]     <_asymmetric_recursive_2>
 # COM:   callq 0x[[#%x,ASYMMETRIC_RECURSIVE_2]]     <_asymmetric_recursive_2>
 # CHECK: callq 0x[[#%x,INIT_2:]]                    <_init_2>
 # CHECK: callq 0x[[#%x,INIT_2:]]                    <_init_2>
 # CHECK: callq 0x[[#%x,INIT_3:]]                    <_init_3>

 
 _check_length_2:
   movq $97, %rax
   .space 1
 
 _my_personality:
   mov $1345, %rax
 
-## No fold: functions have unwind info.
-## FIXME: Fold functions with identical unwind info.
+## Functions with identical unwind info should be folded.
 _has_unwind_1:
   .cfi_startproc
   .cfi_personality 155, _my_personality
   .cfi_def_cfa_offset 16
   ret
   .cfi_endproc
 
 _has_unwind_2:
   .cfi_startproc
   .cfi_personality 155, _my_personality
   .cfi_def_cfa_offset 16
   ret
   .cfi_endproc
 
+## This function has different unwind info from the preceding two, and therefore
+## should not be folded.
+_has_unwind_3:
+  .cfi_startproc
+  .cfi_personality 155, _my_personality
+  .cfi_def_cfa_offset 8
+  ret
+  .cfi_endproc
+
 ## Fold: Mutually-recursive functions with symmetric bodies
 _mutually_recursive_1:
   callq _mutually_recursive_1 # call myself
   callq _mutually_recursive_2 # call my twin
 
 _mutually_recursive_2:
   callq _mutually_recursive_2 # call myself
   callq _mutually_recursive_1 # call my twin
_main:
   callq _defined_ref_with_addend_2
   callq _recursive
   callq _call_recursive_1
   callq _call_recursive_2
   callq _check_length_1
   callq _check_length_2
   callq _has_unwind_1
   callq _has_unwind_2
+  callq _has_unwind_3
   callq _mutually_recursive_1
   callq _mutually_recursive_2
   callq _asymmetric_recursive_1
   callq _asymmetric_recursive_2
   callq _init_1
   callq _init_2
   callq _init_3