[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–1209

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

s/at all/are all/

lld/MachO/InputSection.cpp

349

clang-format

lld/MachO/ICF.cpp

void macho::foldIdenticalSections() {
   // 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)
           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

lld/MachO/InputFiles.cpp

ArrayRef<data_in_code_entry> ObjFile::getDataInCode() const {
   return {reinterpret_cast<const data_in_code_entry *>(buf + c->dataoff),
           c->datasize / sizeof(data_in_code_entry)};
 }
 
 // Create pointers from symbols to their associated compact unwind entries.
 void ObjFile::registerCompactUnwind(Section &compactUnwindSection) {
   for (const Subsection &subsection : compactUnwindSection.subsections) {
     ConcatInputSection *isec = cast<ConcatInputSection>(subsection.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);
+    // Hack!! Each compact unwind entry (CUE) has its UNSIGNED relocations embed
+    // their addends in its data. Thus if ICF operated naively and compared the
+    // entire contents of each CUE, entries with identical unwind info but e.g.
+    // belonging to different functions would never be considered equivalent. To
+    // work around this problem, we remove some parts of the data containing the
+    // embedded addends. In particular, we remove the function address and LSDA
+    // pointers.  Since these locations are at the start and end of the entry,
+    // we can do this using a simple, efficient slice rather than performing a
+    // copy.  We are not losing any information here because the embedded
+    // addends have already been parsed in the corresponding Reloc structs.
+    //
+    // Removing these pointers would not be safe if they were pointers to
+    // absolute symbols. In that case, there would be no corresponding
+    // relocation. However, (AFAIK) MC cannot emit references to absolute
+    // symbols for either the function address or the LSDA. However, it *can* do
+    // so for the personality pointer, so we are not slicing that field away.
+    //
+    // Note that we do not adjust the offsets of the corresponding relocations;
+    // instead, we rely on `relocateCompactUnwind()` to correctly handle these
+    // truncated input sections.
+    isec->data = isec->data.slice(target->wordSize, 8 + target->wordSize);
     uint32_t encoding = read32le(isec->data.data() + sizeof(uint32_t));
     // llvm-mc omits CU entries for functions that need DWARF encoding, but
     // `ld -r` doesn't. We can ignore them because we will re-synthesize these
     // CU entries from the DWARF info during the output phase.
     if ((encoding & target->modeDwarfEncoding) == target->modeDwarfEncoding)
       continue;
 
     ConcatInputSection *referentIsec;

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,HAS_ABS_PERSONALITY_1:]]     l     F __TEXT,__text _has_abs_personality_1
+# CHECK: [[#%x,HAS_ABS_PERSONALITY_2:]]     l     F __TEXT,__text _has_abs_personality_2
 # CHECK: [[#%x,HAS_EH_FRAME_1:]]            l     F __TEXT,__text _has_eh_frame_1
 # CHECK: [[#%x,HAS_EH_FRAME_2:]]            l     F __TEXT,__text _has_eh_frame_2
 # CHECK: [[#%x,HAS_EH_FRAME_3:]]            l     F __TEXT,__text _has_eh_frame_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: [[#%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 that we don't accidentally dedup distinct EH frames.
 # CHECK: FDE {{.*}} pc=[[#%x,HAS_EH_FRAME_1]]
 # CHECK: FDE {{.*}} pc=[[#%x,HAS_EH_FRAME_2]]
 # CHECK: FDE {{.*}} pc=[[#%x,HAS_EH_FRAME_3]]
 
 # CHECK-LABEL: Disassembly of section __TEXT,__text:
 # CHECK:        <_main>:

 # 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,HAS_ABS_PERSONALITY_1]]     <_has_abs_personality_1>
+# CHECK: callq 0x[[#%x,HAS_ABS_PERSONALITY_2]]     <_has_abs_personality_2>
 # CHECK: callq 0x[[#%x,HAS_EH_FRAME_1]]            <_has_eh_frame_1>
 # CHECK: callq 0x[[#%x,HAS_EH_FRAME_2]]            <_has_eh_frame_2>
 # CHECK: callq 0x[[#%x,HAS_EH_FRAME_3]]            <_has_eh_frame_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>

 
 _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
+
+## The next two functions should not be folded as they refer to personalities
+## at different absolute addresses. This verifies that we are doing the right
+## thing in our "data slicing hack" for compact unwind.
+_has_abs_personality_1:
+  .cfi_startproc
+  .cfi_personality 155, _abs_personality_1
+  .cfi_def_cfa_offset 16
+  ret
+  .cfi_endproc
+
+_has_abs_personality_2:
+  .cfi_startproc
+  .cfi_personality 155, _abs_personality_2
+  .cfi_def_cfa_offset 16
+  ret
+  .cfi_endproc
+
+_abs_personality_1 = 0x1
+_abs_personality_2 = 0x2
+
 ## In theory _has_eh_frame_{1, 2} can be dedup'ed, but we don't support this
 ## yet.
 _has_eh_frame_1:
   .cfi_startproc
   .cfi_def_cfa_offset 8
   ## cfi_escape cannot be encoded in compact unwind
   .cfi_escape 0x2e, 0x10
   ret
_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 _has_abs_personality_1
+  callq _has_abs_personality_2
   callq _has_eh_frame_1
   callq _has_eh_frame_2
   callq _has_eh_frame_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
+
+.section __TEXT,__gcc_except_tab
+GCC_except_table0:
+Lexception0:
+  .byte 255
+
+GCC_except_table1:
+Lexception1:
+  .byte 255
+
+GCC_except_table2:
+Lexception2:
+  .byte 254