[lld-macho] Support folding of functions with identical LSDAs

[int3]

Summary

To do this, we need to slice away the LSDA pointer, just like we are
slicing away the functionAddress pointer.

No observable difference in perf on chromium_framework:

           base           diff           difference (95% CI)
sys_time   1.769 ± 0.068  1.761 ± 0.065  [  -2.7% ..   +1.8%]
user_time  9.517 ± 0.110  9.528 ± 0.116  [  -0.6% ..   +0.8%]
wall_time  8.291 ± 0.174  8.307 ± 0.183  [  -1.1% ..   +1.5%]
samples    21             25

[int3]

rebase

[int3]

trying alternative approach

[int3]

better approach

[thakis]

lg, i think

lld/MachO/InputFiles.cpp

1189 ↗

(On Diff #445097)

nit: maybe spell out CUE once? afaict nothing in lld/MachO spells it out (I assume it's "compact unwind entry", but it's not totally obvious imho)

1195 ↗

(On Diff #445097)

s/at all/are all/

lld/MachO/InputSection.cpp

349

clang-format

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");
     }
   }
 }
 
+// We can ignore embedded addends when doing ICF because we have already mapped
+// their raw values to Reloc structs during the parsing phase. We usually leave
+// the embedded addends in InputSection::data instead of zeroing them out, as
+// this is expensive. However, these embedded addends can cause ICF to miss
+// folding opportunities, because while different addends can resolve to the
+// same output VA, ICF can't see that while doing its naive hashing / equality
+// checks.
+//
+// We compromise by zeroing out embedded addends for sections where it is likely
+// to expose a lot more folding opportunities.
+static void clearEmbeddedAddends(InputSection *isec) {
+  // We have to do this copying serially as the BumpPtrAllocator is not
+  // thread-safe. FIXME: Make a thread-safe allocator.
+  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;
+}
+
 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.
 
   // 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 = (isCodeSection(isec) || isCfStringSection(isec) ||
-                       isClassRefsSection(isec)) &&
-                      !isec->keepUnique && !isec->shouldOmitFromOutput() &&
-                      sectionType(isec->getFlags()) == MachO::S_REGULAR;
+    bool isHashable =
+        (isCodeSection(isec) || isCfStringSection(isec) ||
+         isClassRefsSection(isec) || isGccExceptTabSection(isec)) &&
     if (isHashable) {
       hashable.push_back(isec);
       for (Defined *d : isec->symbols)
-        if (d->unwindEntry)
+        if (d->unwindEntry) {
+          clearEmbeddedAddends(d->unwindEntry);
           hashable.push_back(d->unwindEntry);
-
-      // __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) || isClassRefsSection(isec)) {
-        // We have to do this copying serially as the BumpPtrAllocator is not
-        // thread-safe. FIXME: Make a thread-safe allocator.
-        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;
         }
+
+      if (isCfStringSection(isec) || isClassRefsSection(isec))
+        clearEmbeddedAddends(isec);
     } else if (!isEhFrameSection(isec)) {
       // EH frames are gathered as hashables from unwindEntry above; give a
       // unique ID to everything else.
       isec->icfEqClass[0] = ++icfUniqueID;
     }
   }
   parallelForEach(hashable, [](ConcatInputSection *isec) {
     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/InputSection.h

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 *);
 bool isEhFrameSection(const InputSection *);
+bool isGccExceptTabSection(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";

lld/MachO/InputSection.cpp

return isec->getName() == section_names::objcClassRefs &&
          isec->getSegName() == segment_names::data;
 }
 
 bool macho::isEhFrameSection(const InputSection *isec) {
   return isec->getName() == section_names::ehFrame &&
          isec->getSegName() == segment_names::text;
 }
 
+bool macho::isGccExceptTabSection(const InputSection *isec) {
+  return isec->getName() == section_names:: gccExceptTab &&
+         isec->getSegName() == segment_names::text;
+}
+
 std::string lld::toString(const InputSection *isec) {
   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
 }

lld/test/MachO/icf.s

 # 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_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,HAS_UNWIND_4:]]              l     F __TEXT,__text _has_unwind_4
 # 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: [[#%x,GCC_EXCEPT_0:]]              l     O __TEXT,__gcc_except_tab GCC_except_table0
+# CHECK: [[#%x,GCC_EXCEPT_0]]               l     O __TEXT,__gcc_except_tab GCC_except_table1
+# CHECK: [[#%x,GCC_EXCEPT_2:]]              l     O __TEXT,__gcc_except_tab GCC_except_table2
 
 # CHECK-LABEL: Disassembly of section __TEXT,__text:
 # CHECK:        <_main>:
 # CHECK: callq 0x[[#%x,ABS1B_REF:]]                 <_abs1b_ref>
 # CHECK: callq 0x[[#%x,ABS1B_REF:]]                 <_abs1b_ref>
 # CHECK: callq 0x[[#%x,ABS1B_REF_WITH_ADDEND:]]     <_abs1b_ref_with_addend>
 # CHECK: callq 0x[[#%x,ABS1B_REF_WITH_ADDEND:]]     <_abs1b_ref_with_addend>
 # CHECK: callq 0x[[#%x,ABS2_REF:]]                  <_abs2_ref>

 # 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_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,HAS_UNWIND_4]]               <_has_unwind_4>
 # 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>

 
 _my_personality:
   mov $1345, %rax
 
 ## Functions with identical unwind info should be folded.
 _has_unwind_1:
   .cfi_startproc
   .cfi_personality 155, _my_personality
+  .cfi_lsda 16, Lexception0
   .cfi_def_cfa_offset 16
   ret
   .cfi_endproc
 
 _has_unwind_2:
   .cfi_startproc
   .cfi_personality 155, _my_personality
+  .cfi_lsda 16, Lexception1
   .cfi_def_cfa_offset 16
   ret
   .cfi_endproc
 
-## This function has different unwind info from the preceding two, and therefore
+## This function has a different cfa_offset from the first two, and therefore
 ## should not be folded.
 _has_unwind_3:
   .cfi_startproc
   .cfi_personality 155, _my_personality
+  .cfi_lsda 16, Lexception1
   .cfi_def_cfa_offset 8
   ret
   .cfi_endproc
 
+## This function has a different LSDA from the first two, and therefore should
+## not be folded.
+_has_unwind_4:
+  .cfi_startproc
+  .cfi_personality 155, _my_personality
+  .cfi_lsda 16, Lexception2
+  .cfi_def_cfa_offset 16
+  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 _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 _has_unwind_4
   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
+
+.section __TEXT,__gcc_except_tab
+GCC_except_table0:
+Lexception0:
+  .byte 255
+
+GCC_except_table1:
+Lexception1:
+  .byte 255
+
+GCC_except_table2:
+Lexception2:
+  .byte 254