[lld-macho] Don't fold subsections with symbols at nonzero offsets

[int3]

Summary

Symbols occur at non-zero offsets in a subsection if they are
.alt_entry symbols, or if .subsections_via_symbols is omitted.

It doesn't seem like ld64 supports folding those subsections either.
Moreover, supporting this it makes foldIdentical a lot more
complicated to implement. The existing implementation has some
questionable behavior around STABS omission -- if a section with an
non-zero offset symbol was folded into one without, we would omit the
STABS entry for the non-zero offset symbol.

I will be following up with a diff that makes foldIdentical zero out
the symbol sizes for folded symbols. Again, this is much easier to
implement if we don't have to worry about non-zero offsets.

[oontvoo]

LG

lld/MachO/InputSection.cpp

147

this comment is stale?

lld/MachO/ICF.cpp

for (ConcatInputSection *isec : inputSections) {
     // NOTE: __objc_selrefs is typically marked as no_dead_strip by MC, but we
     // can still fold it.
     bool hasFoldableFlags = (isSelRefsSection(isec) ||
                              sectionType(isec->getFlags()) == MachO::S_REGULAR);
     // FIXME: consider non-code __text sections as foldable?
     bool isFoldable = (!onlyCfStrings || isCfStringSection(isec)) &&
                       (isCodeSection(isec) || isFoldableWithAddendsRemoved ||
                        isGccExceptTabSection(isec)) &&
-                      !isec->keepUnique && !isec->shouldOmitFromOutput() &&
-                      hasFoldableFlags;
+                      !isec->keepUnique && !isec->hasAltEntry &&
+                      !isec->shouldOmitFromOutput() && hasFoldableFlags;
     if (isFoldable) {
       foldable.push_back(isec);
       for (Defined *d : isec->symbols)
         if (d->unwindEntry)
           foldable.push_back(d->unwindEntry);
 
       // Some sections have embedded addends that foil ICF's hashing / equality
       // checks. (We can ignore embedded addends when doing ICF because the same

lld/MachO/InputFiles.cpp

for (size_t j = 0; j < symbolIndices.size(); ++j) {
       //   1. If the input file does not use subsections-via-symbols.
       //   2. Multiple symbols at the same address only induce one subsection.
       //      (The symbolOffset == 0 check covers both this case as well as
       //      the first loop iteration.)
       //   3. Alternative entry points do not induce new subsections.
       //   4. If we have a literal section (e.g. __cstring and __literal4).
       if (!subsectionsViaSymbols || symbolOffset == 0 ||
           sym.n_desc & N_ALT_ENTRY || !isa<ConcatInputSection>(isec)) {
+        isec->hasAltEntry = symbolOffset != 0;
         symbols[symIndex] = createDefined(sym, name, isec, symbolOffset,
                                           symbolSize, forceHidden);
         continue;
       }
       auto *concatIsec = cast<ConcatInputSection>(isec);
 
       auto *nextIsec = make<ConcatInputSection>(*concatIsec);
       nextIsec->wasCoalesced = false;

lld/MachO/InputSection.h

public:
   virtual bool isLive(uint64_t off) const = 0;
   virtual void markLive(uint64_t off) = 0;
   virtual InputSection *canonical() { return this; }
   virtual const InputSection *canonical() const { return this; }
 
 protected:
   InputSection(Kind kind, const Section &section, ArrayRef<uint8_t> data,
                uint32_t align)
-      : sectionKind(kind), align(align), data(data), section(section) {}
+      : sectionKind(kind), keepUnique(false), hasAltEntry(false), align(align),
+        data(data), section(section) {}
 
   InputSection(const InputSection &rhs)
-      : sectionKind(rhs.sectionKind), align(rhs.align), data(rhs.data),
-        section(rhs.section) {}
+      : sectionKind(rhs.sectionKind), keepUnique(false), hasAltEntry(false),
+        align(rhs.align), data(rhs.data), section(rhs.section) {}
 
   Kind sectionKind;
 
 public:
   // is address assigned?
   bool isFinal = false;
   // keep the address of the symbol(s) in this section unique in the final
   // binary ?
-  bool keepUnique = false;
+  bool keepUnique : 1;
+  // Does this section have symbols at offsets other than zero? (NOTE: only
+  // applies to ConcatInputSections.)
+  bool hasAltEntry : 1;
   uint32_t align = 1;
 
   OutputSection *parent = nullptr;
   ArrayRef<uint8_t> data;
   std::vector<Reloc> relocs;
   // The symbols that belong to this InputSection, sorted by value. With
   // .subsections_via_symbols, there is typically only one element here.
   llvm::TinyPtrVector<Defined *> symbols;

lld/MachO/InputSection.cpp

 void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
   align = std::max(align, copy->align);
   copy->live = false;
   copy->wasCoalesced = true;
   copy->replacement = this;
   for (auto &copySym : copy->symbols)
     copySym->wasIdenticalCodeFolded = true;
 
-  // Merge the sorted vectors of symbols together.
-  auto it = symbols.begin();
-  for (auto copyIt = copy->symbols.begin(); copyIt != copy->symbols.end();) {
-    if (it == symbols.end()) {
-      symbols.push_back(*copyIt++);
-      it = symbols.end();
-    } else if ((*it)->value > (*copyIt)->value) {
-      std::swap(*it++, *copyIt);
-    } else {
-      ++it;
-    }
-  }
+  symbols.insert(symbols.end(), copy->symbols.begin(), copy->symbols.end());
   copy->symbols.clear();
 
   // Remove duplicate compact unwind info for symbols at the same address.
   if (symbols.empty())
     return;
-  it = symbols.begin();
-  uint64_t v = (*it)->value;
-  for (++it; it != symbols.end(); ++it) {
-    Defined *d = *it;
-    if (d->value == v)
-      d->unwindEntry = nullptr;
-    else
-      v = d->value;
+  for (auto it = symbols.begin() + 1; it != symbols.end(); ++it) {
+    assert((*it)->value == 0);
+    (*it)->unwindEntry = nullptr;
   }
 }
 
 void ConcatInputSection::writeTo(uint8_t *buf) {
   assert(!shouldOmitFromOutput());
 
   if (getFileSize() == 0)
     return;

lld/test/MachO/icf.s

 # CHECK: [[#%x,ABS2_REF:]]                  l     F __TEXT,__text _abs2_ref
 # CHECK: [[#%x,NOT_ABS_REF:]]               l     F __TEXT,__text _not_abs_ref
 # CHECK: [[#%x,DYLIB_REF_2:]]               l     F __TEXT,__text _dylib_ref_1
 # CHECK: [[#%x,DYLIB_REF_2]]                l     F __TEXT,__text _dylib_ref_2
 # CHECK: [[#%x,DYLIB_REF_3:]]               l     F __TEXT,__text _dylib_ref_3
 # CHECK: [[#%x,DYLIB_REF_4:]]               l     F __TEXT,__text _dylib_ref_4
 # CHECK: [[#%x,ALT:]]                       l     F __TEXT,__text _alt
 # CHECK: [[#%x,WITH_ALT_ENTRY:]]            l     F __TEXT,__text _with_alt_entry
-# CHECK: [[#%x,WITH_ALT_ENTRY]]             l     F __TEXT,__text _no_alt_entry
+# CHECK: [[#%x,NO_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,DEFINED_REF_WITH_ADDEND_3:]] l     F __TEXT,__text _defined_ref_with_addend_3
 # 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: callq 0x[[#%x,ABS2_REF]]                  <_abs2_ref>
 # CHECK: callq 0x[[#%x,NOT_ABS_REF]]               <_not_abs_ref>
 # CHECK: callq 0x[[#%x,DYLIB_REF_2]]               <_dylib_ref_2>
 # CHECK: callq 0x[[#%x,DYLIB_REF_2]]               <_dylib_ref_2>
 # CHECK: callq 0x[[#%x,DYLIB_REF_3]]               <_dylib_ref_3>
 # CHECK: callq 0x[[#%x,DYLIB_REF_4]]               <_dylib_ref_4>
 # CHECK: callq 0x[[#%x,ALT]]                       <_alt>
 # CHECK: callq 0x[[#%x,WITH_ALT_ENTRY]]            <_with_alt_entry>
-# CHECK: callq 0x[[#%x,WITH_ALT_ENTRY]]            <_with_alt_entry>
+# CHECK: callq 0x[[#%x,NO_ALT_ENTRY]]              <_no_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,DEFINED_REF_WITH_ADDEND_3]] <_defined_ref_with_addend_3>
 # 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>
_dylib_ref_3:
   mov ___inf@GOTPCREL(%rip), %rax
   callq ___inf
 
 ## No fold: referent dylib addend differs
 _dylib_ref_4:
   mov ___nan + 1@GOTPCREL(%rip), %rax
   callq ___inf + 1
 
-## We can merge two sections even if one of them has an alt entry. Just make
-## sure we don't merge the alt entry symbol with a regular symbol.
+## Sections with alt entries cannot be merged.
 .alt_entry _alt
 _with_alt_entry:
   movq $3132, %rax
 _alt:
   ret
 
 _no_alt_entry:
   movq $3132, %rax